LeetCode 206. 反转链表 & 剑指offer 面试题24. 反转链表（易）

链表的基础操作，递归、循环两种形式都必须要会手写。

链表

206. 反转链表

题目

反转一个单链表。

示例: 

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

测试用例

输入的链表头指针是 nullptr。 输入的链表只有一个节点。 输入的链表有多个节点。

直觉

1、递归

递归是从后往前递归的，假设后面一部分已经反转好，现在要反转前面一部分。递归的最后一层就是 tail，tail 被逐层 return。

假设列表为：

\[ n_{1}\rightarrow ... \rightarrow n_{k-1} \rightarrow n_{k} \rightarrow n_{k+1} \rightarrow ... \rightarrow n_{m} \rightarrow \mbox{None} \]

若从节点 \(n_{k+1}\) 到 \(n_{m}\) 已经被反转，而我们正处于 \(n_{k}\)。

\[ n_{1}\rightarrow ... \rightarrow n_{k-1} \rightarrow n_{k} \rightarrow n_{k+1} \leftarrow ... \leftarrow n_{m} \]

我们希望 \(n_{k+1}\)的下一个节点指向 \(n_{k}\)，所以 \(n_{k}.next.next = n_{k}\)。

要小心的是 \(n_{1}\) 的下一个必须指向 None 。如果你忽略了这一点，你的链表中可能会产生循环。如果使用大小为 2 的链表测试代码，则可能会捕获此错误。

2、循环

更新 pre_p、p、next_p 四个指针，设置哑节点，每次把要反转的 p 节点指向 pre_p ，先利用 p 更新 pre_p，再利用 next_p 更新 p 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  A -> B -> C -> D
  ^    ^    ^  
pre_p  p  next_p
     cur_p

# p.next = pre_p
  A <- B    C -> D
  ^    ^    ^  
pre_p  p  next_p
     cur_p

# p = p_next
  A <- B    C -> D
  ^    ^    ^  
pre_p cur_p p
          next_p
     
# pre_p = cur_p
  A <- B    C -> D
       ^    ^  
     cur_p  p
     pre_p next_p

关键的7行代码

1
2
3
4
5
6
7
while p:  # 保留 pre_p、p/cur_p、next_p四个指针
    next_p = p.next  # 保留下一个位置
    cur_p = p  # 保留当前位置
    p.next = pre_p  # 当前节点断开与后续节点的链接，反向链接前一个节点。  
    p = next_p  # p指针依靠next_p向后移动
    pre_p = cur_p  # pre_p依靠cur_p指针向后移动
head.next = None  # 这一步很重要，之前的head已经变成tail了，所以要把head.next设置为None

特别注意 head.next = None

代码

递归

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:      # 1
        """reverse Linked List
        :param head: ListNonde
        :return: ListNonde
        """
        if head == None or head.next == None:  return head  # 2
        p = self.reverseList(head.next)                     # 3
        head.next.next = head                               # 4
        head.next = None                                    # 5
        return p                                            # 6

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:       # 1
        """reverse Linked List
        :param head: ListNonde
        :return: ListNonde
        """
        if head == None or head.next == None:  return head   # 2
        dummy = ListNode(None)                               # 3
        dummy.next = head                                    # 4
        pre_p = dummy                                        # 5
        p = head                                             # 6
        while p:                                             # 7
            next_p = p.next                                  # 8
            p.next = pre_p                                   # 9
            pre_p = p                                        # 10
            p = next_p                                       # 11
        # 这一步很重要，之前的head已经变成tail了，所以要把head.next设置为None
        head.next = None                                     # 12
        return pre_p                                         # 13