题目

思路

一句话：逐个把每个节点的 next 从“指后”改成“指前”，一趟扫完就反转完成。

最直白的想法：把节点值依次存进数组，再从尾到头新建一条链表、依次输出。这要 O(n) 时间、O(n) 空间；更麻烦的是它复制的是“值”、丢的是“原节点身份”——后续很多题目、面试场景都要求原地改指针，这条路走不通。

想保留原节点原地反转时，最容易想岔的做法是“每次找到当前尾节点，把它摘下来接到新头上”。由于链表不能随机访问，每摘一个尾节点都要从头走到尾，定位尾节点及其前驱，总体约 O(n²)，明显太慢。

关键观察：反转整条链表，等价于把 n - 1 条 next 边全部反向；每条边其实只需要动一次。唯一要防的坑只有一个——把 curr.next 改掉之后，原来的后继就找不到了，所以动手前先把它存进临时变量 nxt。

于是用一对“可见”指针 prev、curr 一前一后交替前进，外加一个暂存 nxt，就能 O(n) 时间、O(1) 空间原地完成。这就是三指针迭代；递归做的是同一件事，只是换成“先跑到链表尾，再从后往前逐个掉头”。

解法

迭代写法：维护 prev（已反转部分的新链头）与 curr（当前待处理节点），每轮执行“存后继 → 掉头 → 平移”三步。

1. 暂存 nxt = curr.next，保住原后继，防止断链。
2. 令 curr.next = prev，把当前节点接到已反转部分的前面。
3. prev = curr、curr = nxt，两指针一并前移。
4. 当 curr 为空时停止，返回 prev。

以 [1,2,3] 为例（“空”表示 nullptr/None）：

curr 变空即结束，此时 prev = 3 就是新链头。

下图把上面 4 个步骤串成流程，并逐步演示：

C++

/**
 * 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;   // 已反转部分的新链头，初始为空
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。