反转链表

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

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
输入：head = [1,2]
输出：[2,1]
输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

方法一：迭代

假设链表为 1→2→3→∅，我们想要把它改成∅←1←2←3。
在遍历链表时，将当前节点的 \textit{next}next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

c++解法：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

c解法:

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。

• 空间复杂度：O(1)。

方法二：

递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？

假设链表为：

$n_{1}$ $\rarr$ ... $n_{k-1}$ $\rarr$ $n_{k}-1$ $\rarr$ $n_{k}$ $\rarr$ $n_{k+1}$ $\rarr$ ...$\rarr$ $n_{m}$ $\rarr$ ∅

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

$n_{1}$ $\rarr$ ... $n_{k-1}$ $\rarr$ $n_{k}-1$ $\rarr$ $n_{k}$ $\rarr$ $n_{k+1}$ $\larr$ ...$\larr$ $n_{m}$ $\larr$ ∅

所以，$n_{k}$.next.next = $n_{k}$ 。

需要注意的是 $n_{1}$的下一个节点必须指向 $\varnothing$。如果忽略了这一点，链表中可能会产生环。

cpp代码:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

c代码：

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

python的递归解法:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head: ListNode) -> ListNode:
         if(head == None or head.next == None):
            return head
         cur = self.reverseList(head.next)

        # 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        # 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
        # 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
        # 等号右侧为 head，意思就是设置 5 的下一个节点是 4

        # 这里出现了两个 next
        # 第一个 next 是「获取」 head 的下一节点
        # 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
         head.next.next = head

        # 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
        # 否则会发生无限循环
         head.next = None

        # 我们把每次反转后的结果传递给上一层
         return cur