📝 题目描述

题目链接：反转链表

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

示例：

示例 1：

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

示例 2：

1
2
输入：head = [1,2]
输出：[2,1]

示例 3：

1
2
输入：head = []
输出：[]

提示：

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

💡 解题思路

方法一：递归

比较容易想到的解法，本质上就是利用函数调用栈状态来记录每个节点。其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？

假设链表为：

n1​→…→nk−1​→nk​→nk+1​→…→nm​→∅n_1​→…→n_{k−1}​→n_{k}​→n_{k+1}​→…→n_{m}​→∅

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

n1​→…→nk−1​→nk​→nk+1←…←nm​→∅n_1​→…→n_{k−1}​→n_{k}​→n_{k+1}←…←n_{m}​→∅

我们希望 nk+1n_{k+1}​ 的下一个节点指向 nkn_{k}​。

所以，nk​.next.next=nk​n_k​.next.next=n_k​。

需要注意的是 n1n_1​ 的下一个节点必须指向 ∅∅。如果忽略了这一点，链表中会产生环。

方法二：迭代

假设链表为 1→2→3→∅1→2→3→∅，我们想要把它改成 ∅←1←2←3∅←1←2←3。

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

🔧 代码实现

1、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseTool (ListNode* ptr) {
        if (ptr == nullptr || ptr -> next == nullptr) {
            return ptr;
        } else {
            ListNode* ans = reverseTool (ptr -> next);
            ptr -> next -> next = ptr;
            ptr -> next = nullptr;
            return ans;
        }
    }
    ListNode* reverseList(ListNode* head) {
        return reverseTool(head);
    }
};

2、迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* current = head, * prev = nullptr;
        while(current != nullptr) {
            ListNode * next = current -> next;
            current -> next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
};

📊 复杂度分析

1、递归

  • 时间复杂度：O(n)O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
  • 空间复杂度：O(n)O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

2、迭代

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

🎯 总结

  • 核心思想：理解迭代的思路。