【Leetcode链表】反转链表（206）

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解答

能用两种方法

• 三个指针，改变指向完成反转
• 用递归，回溯完成节点的指向反转

通过代码如下：

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

# 用三个指针，前一个p，当前c，后一个n

class Solution:

    def reverseList(self, head: ListNode) -> ListNode:

        c, p = head, None  # p初始是Null节点

        while c:

            # n = c.next  # 当前节点后一个

            # c.next = p  # 重要，当前节点指向后一个

            # p = c       # 后移前节点，为当前节点c后移做准备

            # c = n       # 后移当前节点

            # 并行，不存在赋值顺序

            # So炫酷的写法，劳资只能照着上面式子改，主要还是笨！

            c.next, p, c = p, c, c.next

        return p

# 时间复杂度O(n)，空间复杂度O(1)

# # 递归解法: 时间复杂度O(n)，空间复杂度O(n)

# class Solution:

#     def reverseList(self, head: ListNode) -> ListNode:

#         if head==None or head.next == None:

#             return head

#         p = self.reverseList(head.next)

#         head.next.next = head

#         head.next = None

#         return p

# # 不妨假设链表为1，2，3，4，5。按照递归，当执行reverseList（5）的时候返回了5这个节点，reverseList(4)中的p就是5这个节点，我们看看reverseList（4）接下来执行完之后，5->next = 4, 4->next = null。这时候返回了p这个节点，也就是链表5->4->null，接下来执行reverseList（3），代码解析为4->next = 3,3->next = null，这个时候p就变成了，5->4->3->null, reverseList(2), reverseList(1)依次类推，p就是:5->4->3->2->1->null