面试常考-链表反转解析

你是否有过这种体会：看别人的代码，当时看得很明白了，但是，过段时间，自己却怎么都写不出来？这是怎么回事，可能我们也清楚。别人的思维你是无法拷贝的，形成之前不具备的思维，刻入骨髓，需要天长日久的思维训练。

leetcode有多重要，无需多言，刷过leetcode的小伙伴，都有以上这些体会。自己想不出来，看完别人的代码，也都看懂了，但是日后再做此题，可能还是搞不定。

就拿链表反转来说，基本是面试的必考题，就是这道题，如果平时没有这方面的训练，思维没有培养起来，也很难在几分钟内准确写出来，不信你现在试试。像这类道题，可能伴随我们整个技术生涯，不分职位高低，它就像水和空气，是程序员应该信手拈来的。

可能还是有些小伙伴，觉得链表等这类知识，自己根本用不到，学这些干啥。亮出一个高逼格的理由，它们会让你coding的思维，更上一层楼。

平常人进阶就得，多思考，多动手，多总结。我也顺手再检测一下，链表反转，我们走起。

迭代版思考过程：

设变量curhead始终指向反转后链表的头部，初始时val等于输入链表头的val, next为None, 即只有1个节点。

此时，原链表头自然指向了第二个节点prehead(如果存在的话)，同时，我们标记其后的节点为tmp，因为接下来我们要破坏prehead的next域，叫它指向我们反转后的新链表头curhead, 所以标记tmp是再自然不过的了。

一旦prehead的next域到curhead建立后，我们新链表就增加了1个节点，正是让curhead指向这个新增节点。

作为迭代，此时我们的prehead就要指向一开始我们标记的tmp了，至此一轮迭代，完美就绪。

明白以上过程，迭代版本的代码1分钟写出来，就不是问题。

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = None
class Solution:    def reverseList(self, head: ListNode) -> ListNode:        if head is None:            return None
        curhead = ListNode(head.val)        prehead = head.next        while prehead is not None:            tmp = prehead.next            prehead.next = curhead                curhead = prehead            prehead = tmp
        return curhead

迭代过程动画演示

下一次，如果再有人问你类似题目，好好给他展示一遍。