反转链表¶

经典数据结构题，考研复试面试题～

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

递归¶

代码¶

最简单的写法就是递归实现：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if (head is None) or (head.next is None):
            return head
        else:
            n = head.next
            head.next = None
            r = self.reverseList(n)
            n.next = head
            return r

先处理边界情况：如果链表长度为0或者1，直接返回即可。

然后进行递归拆分。

图解¶

例如：

graph LR
    head-.->1-->2-->3-->4-->Null

首先把1和1的子节点单独拿出来分别记录为head和n，把1的子节点设置为空：

graph LR
    head-.->1-->Null
    n-.->2-->3-->4-->Null

然后反转字链表n得到r，这时候n指针依然不动：

graph LR
    head-.->1-->Null
    r-.->4-->3-->2-->Null
    n-.->2

最后做一个拼接就完成了：

n.next = head

时间复杂度：$\mathcal{O}(N)$，需要对链表的每个节点进行反转操作。

空间复杂度：$\mathcal{O}(N)$，空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

双指针迭代¶

代码¶

用双指针即可直接进行迭代：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr is not None:
            n = curr.next
            curr.next = prev
            prev = curr
            curr = n
        return prev

图解¶

例如：

graph LR
    head-.->1-->2-->3-->4-->Null

先定义双指针：

graph LR
    1-->2-->3-->4-->Null
    curr-.->1
    n-.->2
    prev-.->Null

如果curr不是空，就向前移动一个位置：

graph LR
    2-->3-->4-->Null
    curr-.->2
    1-->Null
    prev-.->1
    n-.->3

以此类推即可：

graph LR
    3-->4-->Null
    2-->1
    curr-.->3
    1-->Null
    prev-.->2
    n-.->4

下一步：

graph LR
    4-->Null
    3-->2-->1-->Null
    curr-.->4
    n-.->Null
    prev-.->3

下一步：

graph LR
    4-->3-->2-->1-->Null
    curr-.->Null
    prev-.->4

此时迭代结束，返回prev即可。

时间复杂度：$\mathcal{O}(N)$，需要遍历一次链表。

空间复杂度：$\mathcal{O}(1)$，只定义了一些指针变量，没有使用额外空间。