反转单链表到底有多少种方法？_单链表如何翻转

这是考察频率非常高的一道题目，在 LeetCode 上可以直接练习，点击《反转链表》。

这道题目，包含了一个最基本的考察点，经典数据结构单链表的实现。链表是由一个一个节点组成的，每个节点有一个数据域和一个Next指针，链表可以用一个头节点来指代。链表的下一个节点在哪里，由 Next 指针决定。

在这个基础知识的基础上，翻转一个链表就变得非常简单，Next 指针本来指向的后继节点，只要让每个节点的 Next 指针都指向前驱节点，那么，再处理好头尾边界，那么就完成了链表的翻转。

从逻辑上理解，题目的解法一目了然，所以，重点考核的能力是编码能力。显然需要写一个循环，将每个指针都翻转方向，但是，这很考验编码的功力和逻辑思维能力。怎么才能有条不紊的逐个翻转指针呢？

解法一：数组法

先遍历链表，将数字都取出来，放到数组里，然后反转数组，重新构造链表。因为单链表的结构过于简单，缺点过于明显，在日常工作中极其少用，而数组是不管用哪种语言的程序员都十分熟悉的接口，所以，想到使用数组代替链表进行操作。如果没有限定时间、空间复杂度，这种方法，很容易一次写正确。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        arr = []
        while head:
            arr.append(head.val)
            head = head.next
        
        p = dummy = ListNode()
        for num in reversed(arr):
            p.next = ListNode(num)
            p = p.next
        
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13

该算法的时间复杂度是 $O(n)$，空间复杂度是 $O(n)$。在面试中，如果只能想到这种方法，是不够的。

解法二：递归法

递归，是设计算法的利器，在这个场景下，也极其简单，可能比解法一还要简单。递归法的关键是，掌握递归方法的设计思路。

设计递归方法的一种核心思路是，将问题规约成一个规模更小的问题，如果可以解决，我们就可以嵌套使用此法直到将问题规约到最平凡的问题。以本题为例，给定一个链表，如何将其规约成更小的问题呢？例如，我们可以去掉一个节点后，将少了一个节点的链表进行反转。

假设我们已经拥有了一个方法 $f$，可以将少了一个节点的链表反转，那么，我们如何将整个链表反转呢？十分简单，先将去掉头节点的链表反转，然后将头节点连接到反转结果的末尾，就完成了整个链表的反转。那么，我们就可以递归调用这个方法 $f$。直到链表只剩下一个节点，或者没有节点。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next: 
            return head
        newHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newHead
1
2
3
4
5
6
7
8

上面的代码里，首先是递归的最平凡用例，空链表，或者链表只有一个节点，可以直接返回。然后，我们将除头节点以外的部分反转，然后我们将头节点连接到新链表的末尾，就大功告成。

递归算法的设计，精巧简单，实现便利，一般都能无往不利。难点一般在于边界条件，以及复杂度分析。比如，上面写的这个算法，边界条件为什么是两个——空链表和单节点链表？因为，我们规约问题的时候，每次去掉一个节点，总会使得链表最终剩余 0 个节点，那么边界条件我们是不是只考虑 0 个节点就行呢？请自行思考。

递归算法的复杂度分析，比较困难，一般需要有算法学习基础才能掌握基本分析方法。但是也有不少取巧的方法，比如在这个例子里，我们可以在脑海里很形象地想象递归栈展开后的情形，每次摘掉一个节点，等着后面的反转，一旦到达末尾节点，所有递归栈逐级返回，显然，时间复杂度是 $O(n)$。空间复杂度是栈的深度，也是 $O(n)$。

解法三：迭代法

一般解决单链表问题的一个窍门，就是画图示意。上图，是一个已经反转了两个节点的链表的反转过程。如图，我们先切断3、4的连接，然后将 3 指向 2。然后将 Tail 和 Head 指针都往前挪。

对于反转单链表这道题目，记住这个算法窍门就是，“把头变成尾巴”，就能完成反转，一开始尾巴是空的，然后把头节点一个一个接到尾巴上，最后，整条链表变成了尾巴。有了这个思路，无论是画图推导，还是代码编写，都会迎刃而解。这个方法也很容易记忆。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        tail = None
        while head:
            temp = head.next
            head.next = tail
            tail = head
            head = temp
        return tail
1
2
3
4
5
6
7
8
9

如上代码，迭代的时候，我们先用一个 temp 变量记住头节点的下一个位置，然后，就可以开始交换，首先将头节点接到尾巴上，然后尾巴往前移，原来的头节点变成了新的尾巴的开始，然后头节点指向一开始暂存 temp 的位置，开始下一轮。Python 支持多重赋值，利用语法糖，这个代码还可以写得更简单。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        tail = None
        while head:
            head.next, tail, head = tail, head, head.next
        return tail
1
2
3
4
5
6

这个写法看着很优雅，但是很不容易写对，也不容易读懂，不是很推荐。

这个算法的复杂度显然是 $O(n)$，空间复杂度 $O(1)$。这个方法是比较高效，一般也是面试中能够出彩的方案。不过，不通过自己推理，多次编写来练习，一般很难写到这么精简。

— END —