Sign in Subscribe
算法

反转链表

loser

• 7 min read
Share

给你单链表的头节点 head。

请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：

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

解法一（迭代）：

/**
 * 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* prev = nullptr;
        ListNode* cur = head;

        while (cur != nullptr)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }
};

解法二（递归）：

/**
 * 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) {
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }

        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }
};

核心思想

这题要求把单链表的方向整体反过来。

单链表只能从当前节点走到下一个节点，也就是只能通过：

cur->next

继续往后访问。

所以反转链表时最关键的问题是：

在修改当前节点的 next 指针之前，必须先保存原来的下一个节点。

否则一旦执行：

cur->next = prev;

原来后面的链表就找不到了。

迭代解法用三个指针完成：

  • prev：已经反转好的链表头
  • cur：当前正在处理的节点
  • next：提前保存的下一个节点

递归解法则是先反转后面的链表，再把当前节点接到后面链表的末尾。

解法一：迭代反转

初始时：

ListNode* prev = nullptr;
ListNode* cur = head;

prev 表示已经反转好的部分。

刚开始还没有任何节点被反转，所以是 nullptr。

每次处理当前节点 cur 时，分三步。

1. 保存下一个节点

ListNode* next = cur->next;

因为马上要改变 cur->next。

如果不先保存，后面的链表就会丢失。

2. 反转当前节点指针

cur->next = prev;

这一步让当前节点指向已经反转好的部分。

3. 两个指针向后移动

prev = cur;
cur = next;

prev 更新为新的反转链表头。

cur 继续处理原链表中的下一个节点。

当 cur == nullptr 时，说明原链表全部处理完。

此时 prev 就是反转后链表的头节点。

解法二：递归反转

递归解法的思路是：

先把 head->next 开始的后半段链表反转好。

例如链表是：

1 -> 2 -> 3 -> 4 -> 5

递归处理 2 -> 3 -> 4 -> 5 后，得到：

5 -> 4 -> 3 -> 2

此时节点 1 还在最前面，并且 1->next 仍然指向节点 2。

要把 1 接到反转后链表的末尾，需要做：

head->next->next = head;
head->next = nullptr;

第一句让节点 2 指回节点 1。

第二句把节点 1 的 next 断开，避免形成环。

递归返回的 newHead 是反转后链表的新头节点，整个过程中保持不变。

边界情况

如果链表为空：

head == nullptr

反转后仍然是空链表，直接返回 nullptr。

如果链表只有一个节点：

head->next == nullptr

反转前后都还是它自己，直接返回 head。

所以递归终止条件是：

if (head == nullptr || head->next == nullptr)
{
    return head;
}

迭代解法也能自然处理这两种情况。

如果 head == nullptr，循环不会执行，最终返回初始的 prev，也就是 nullptr。

如果只有一个节点，循环执行一次后返回这个节点。

为什么不会丢失后续节点

迭代解法中，在修改 cur->next 之前会先保存：

ListNode* next = cur->next;

这样即使当前节点的指针被反转了，仍然可以通过 next 找到原链表中还没处理的部分。

递归解法中，先递归反转 head->next 后面的链表。

也就是说，在修改当前节点 head 的指针之前，后半段链表已经处理完成，并且新头节点已经保存在：

ListNode* newHead = reverseList(head->next);

所以两种解法都不会丢失链表节点。

正确性证明

我们证明：两个算法返回的链表都是原链表的反转结果。

结论 1：迭代过程中，prev 始终是已经处理部分的反转链表头

初始时，没有节点被处理，prev = nullptr，结论成立。

每次循环处理节点 cur 时，先保存原来的后继节点 next。

然后执行：

cur->next = prev;

这会把当前节点接到已经反转好的部分前面。

接着执行：

prev = cur;
cur = next;

于是已经处理的部分多了一个节点，并且方向仍然全部反转。

所以每轮循环结束后，prev 仍然是已经处理部分的反转链表头。

结论 2：迭代结束时，prev 是整个链表的反转结果

循环结束条件是：

cur == nullptr

这说明原链表中的所有节点都已经被处理。

根据结论 1，prev 是已经处理部分的反转链表头。

由于已经处理部分就是整个原链表，所以 prev 是整个链表反转后的头节点。

结论 3：递归算法能正确反转以 head 为头的链表

当链表为空或只有一个节点时，直接返回 head，结果显然正确。

当链表长度大于 1 时，递归调用：

ListNode* newHead = reverseList(head->next);

根据递归假设，head->next 开始的后半段链表已经被正确反转。

此时原来的第二个节点位于反转后链表的末尾。

执行：

head->next->next = head;
head->next = nullptr;

就把当前节点 head 接到了反转后链表的末尾。

因此以 head 为头的整个链表也被正确反转。

得出结论

由结论 1 和结论 2 可知，迭代解法正确。

由结论 3 可知，递归解法正确。

因此两个解法都能返回反转后的链表。

举例理解

以：

head = [1,2,3,4,5]

为例，看迭代过程。

初始：

prev = null
cur  = 1 -> 2 -> 3 -> 4 -> 5

处理节点 1：

prev = 1 -> null
cur  = 2 -> 3 -> 4 -> 5

处理节点 2：

prev = 2 -> 1 -> null
cur  = 3 -> 4 -> 5

处理节点 3：

prev = 3 -> 2 -> 1 -> null
cur  = 4 -> 5

继续处理完所有节点后：

prev = 5 -> 4 -> 3 -> 2 -> 1 -> null
cur  = null

此时返回 prev，得到：

[5,4,3,2,1]

复杂度分析

解法一

每个节点只会被访问一次，每次只做常数次指针修改。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

解法二

每个节点也只会被递归处理一次。

递归调用栈深度等于链表长度。

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

其中 n 是链表中的节点数。

如果只考虑进阶中的两种写法，迭代解法空间更优。