企业官网建设流程全解析

• 示例工程

导读

本文围绕《剑指 Offer（第 2 版）》面试题 24「反转链表」展开，这道题是链表类面试题中最基础、最高频的考点之一，要求在不使用额外数组的前提下，仅通过改写指针完成链表反转。读完本文，你将掌握「头插法（迭代）」与「递归」两种解法各自的核心思想、指针操作细节、复杂度分析，以及它们在 Python3、Java、C++、Go、TypeScript、Rust、JavaScript、C#、Swift 共 9 种主流语言下的完整可运行实现。本文内容以仓库中的 题目题解文档 为主体，并辅以仓库内 Solution 系列源码 进行逐一印证。

一、题目描述与约束条件

1.1 题目要求

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例：

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

1.2 题目背景

本题与主站 206. 反转链表 完全相同，属于「链表」标签下的经典入门题，难度为简单。在《剑指 Offer（第 2 版）》系列中，它位于 lcof 题解目录 的链表专题里，与 面试题 18. 删除链表的节点、面试题 22. 链表中倒数第 k 个节点、面试题 25. 合并两个排序的链表、面试题 35. 复杂链表的复制、面试题 52. 两个链表的第一个公共节点 等题目共同构成一条完整的链表刷题链路。

核心难点：反转的本质是「把每个节点的next指向上一个节点」。难点不在于思路本身，而在于指针操作的顺序——如果不先暂存后继节点就修改next，链表会当场断开，导致后续节点丢失。两种解法（头插法、递归）分别给出了不同的"安全改写指针"策略。

二、方法一：头插法（迭代）

2.1 算法思路

思考：反转即把每个结点的next指向上一个。从头依次摘下结点，用头插法接到哑结点后面，遍历结束时哑结点之后即新头。

具体做法：创建虚拟头节点dummy，遍历链表，将每个节点依次插入dummy的下一个节点。遍历结束，返回dummy.next。

为什么需要虚拟头节点dummy？

• 反转过程中，新链表的头节点会不断变化（每插入一个节点，它都变成新的"头"），使用dummy作为固定的哨兵，可以让每次头插都统一为curr.next = dummy.next; dummy.next = curr两个指针操作，无需单独维护"上一个节点"变量；
• 空链表（head == null）时直接返回dummy.next即为null，天然覆盖边界；
• dummy本身不存储业务数据，仅作为辅助哨兵，最终结果返回dummy.next，不会混入结果链表。

执行过程演示（以1->2->3->4->5->NULL为例）：

每次插入前必须先用临时变量保存curr.next（即原链表的后继），因为curr.next = dummy.next会覆盖掉它，这正是头插法唯一的"坑"，也是所有语言实现中共同的指针处理顺序。

2.2 多语言实现

以下代码与仓库 README.md 中的实现完全一致，仓库对应源码见 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs、Solution.swift。

Python3

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head: ListNode) -> ListNode: dummy = ListNode() curr = head while curr: next = curr.next curr.next = dummy.next dummy.next = curr curr = next return dummy.next

Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode dummy = new ListNode(0); ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = dummy.next; dummy.next = curr; curr = next; } return dummy.next; } }

C++

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* dummy = new ListNode(0); ListNode* curr = head; while (curr) { ListNode* next = curr->next; curr->next = dummy->next; dummy->next = curr; curr = next; } return dummy->next; } };

Go

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseList(head *ListNode) *ListNode { dummy := &ListNode{} curr := head for curr != nil { next := curr.Next curr.Next = dummy.Next dummy.Next = curr curr = next } return dummy.Next }

TypeScript

/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function reverseList(head: ListNode | null): ListNode | null { const dummy = new ListNode(0); let curr = head; while (curr) { const next = curr.next; curr.next = dummy.next; dummy.next = curr; curr = next; } return dummy.next; }

Rust

// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { // pub val: i32, // pub next: Option<Box<ListNode>> // } // // impl ListNode { // #[inline] // fn new(val: i32) -> Self { // ListNode { // next: None, // val // } // } // } impl Solution { pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> { let mut pre = None; let mut cur = head; while let Some(mut node) = cur { cur = node.next.take(); node.next = pre.take(); pre = Some(node); } pre } }

Rust 实现说明：由于Option<Box<ListNode>>的语义限制，Rust 版本采用了「双指针迭代」的等价写法——pre指向已反转部分的头，cur依次取下原链表节点并接到pre之前。它和头插法本质一致（node.next = pre.take()等价于curr.next = dummy.next，pre = Some(node)等价于dummy.next = curr），只是把dummy哨兵换成了可空的前驱指针，最终返回pre。其中take()的作用是把Option中的值取出并原地置为None，从而在不违反所有权规则的前提下安全改写指针。

JavaScript

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { const dummy = new ListNode(0); let curr = head; while (curr) { const next = curr.next; curr.next = dummy.next; dummy.next = curr; curr = next; } return dummy.next; };

C#

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode ReverseList(ListNode head) { ListNode dummy = new ListNode(0); ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = dummy.next; dummy.next = curr; curr = next; } return dummy.next; } }

Swift

/* public class ListNode { * var val: Int * var next: ListNode? * init(_ val: Int) { * self.val = val * self.next = nil * } * } */ class Solution { func reverseList(_ head: ListNode?) -> ListNode? { let dummy = ListNode(0) var curr = head while curr != nil { let next = curr?.next curr?.next = dummy.next dummy.next = curr curr = next } return dummy.next } }

2.3 复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为链表的长度。只需一次遍历，每个节点执行常数次指针操作；
• 空间复杂度：$O(1)$，除dummy与临时变量外不依赖额外存储，不随链表长度增长。

三、方法二：递归

3.1 算法思路

思考：头插法为迭代。递归先反转后续链表，再把当前结点接到已反转部分的尾部，并断开原next。多用一层调用栈。

具体做法：递归反转链表的第二个节点到尾部的所有节点，然后head插在反转后的链表的尾部。

为什么递归可行？

• 递归的返回值ans是「后半段链表反转后的新头」，即原链表尾节点；
• 关键指针操作是head.next.next = head：反转后的后半段链表，其尾节点正是原来的head.next，把head挂到这个尾节点之后，就完成了当前节点的接入；
• 最后必须执行head.next = null断开原指向，否则原链表的第一个节点与第二个节点之间会形成环；
• 递归出口：head为null（空链表）或head.next为null（单节点链表）时，链表已经"反转完成"，直接返回head。

执行过程演示（以1->2->3->4->5->NULL为例）：

1. reverseList(1)：先调用reverseList(2)，得到反转后的5->4->3->2（ans = 5）；
2. 执行1.next.next = 1，即2.next = 1，得到5->4->3->2->1；
3. 执行1.next = null断开原1->2的指向，链表变为5->4->3->2->1->NULL，返回5。

整个递归过程从后往前逐步"拆链再挂链"，与头插法从前往后逐个头插形成对称的两种视角。

3.2 多语言实现

以下代码同样与仓库 README.md 中的实现完全一致，仓库对应源码见 Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts、Solution2.js、Solution2.cs。

Python3

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

Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode ans = reverseList(head.next); head.next.next = head; head.next = null; return ans; } }

C++

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if (!head || !head->next) { return head; } ListNode* ans = reverseList(head->next); head->next->next = head; head->next = nullptr; return ans; } };

Go

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } ans := reverseList(head.Next) head.Next.Next = head head.Next = nil return ans }

TypeScript

/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function reverseList(head: ListNode | null): ListNode | null { if (!head || !head.next) { return head; } const ans = reverseList(head.next); head.next.next = head; head.next = null; return ans; }

JavaScript

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { if (!head || !head.next) { return head; } const ans = reverseList(head.next); head.next.next = head; head.next = null; return ans; };

C#

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode ReverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode ans = ReverseList(head.next); head.next.next = head; head.next = null; return ans; } }

3.3 复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为链表的长度。每个节点只被访问常数次；
• 空间复杂度：$O(n)$。递归深度为链表长度 $n$，系统调用栈占用线性空间，这是递归方法与头插法（$O(1)$ 空间）之间最本质的差异。

四、两种解法对比与面试要点

面试追问提示：主站 206. 反转链表 在提示中明确要求「链表可以选用迭代或递归方式完成反转，你能否用两种方法解决这道题」，与本题解法要求一致。建议面试时先讲头插法（直观、常数空间），再补充递归写法并主动指出其空间代价，体现对时间/空间权衡的完整认知。

五、边界情况与易错点总结

1. 空链表：head == null时，头插法直接返回dummy.next（即null），递归直接命中出口返回head，两种写法均天然安全；
2. 单节点链表：head.next == null时无需反转，直接返回原头节点；
3. 先暂存后继再改写指针：头插法中next = curr.next必须放在curr.next = dummy.next之前，否则原链表后半段会丢失；
4. 递归务必断开原 next：head.next = null不可省略，否则1与2之间会残留双向引用形成环；
5. dummy 的初始值：Java/C++/TS 等语言中dummy的val可用0占位（题解中即如此），该值不会进入结果链表，不影响正确性；
6. 节点个数上限 5000：在本题限制下递归栈深最多约 5000 层，常规环境可以承受；但若数据规模更大，应优先选择迭代写法，避免栈溢出。

六、仓库源码印证

仓库中该题目录 lcof/面试题24. 反转链表 下共 17 个文件，其中：

• Solution.*（9 个文件）对应头插法实现，覆盖 Python3、Java、C++、Go、TypeScript、Rust、JavaScript、C#、Swift，与上文方法一代码一一对应；
• Solution2.*（7 个文件）对应递归实现，覆盖 Python3、Java、C++、Go、TypeScript、JavaScript、C#，与上文方法二代码一一对应；
• README.md/README_EN.md为题目与解法的双语说明文档（本文即基于其中文版展开）。

例如 Solution.go 与 Solution2.go 分别保存了 Go 语言的头插法与递归版本，可直接复制到 LeetCode 在线编辑器运行验证。你可以将该目录作为「一题多解、多语言」的完整参考样例，自行逐语言对照学习指针操作的共性（暂存后继 → 改写指向 → 移动游标）与差异（如 Rust 的所有权转移、Swift 的可选链）。

七、延伸学习建议

反转链表是许多进阶链表题的基础操作，掌握后可顺带完成以下仓库内的关联题目，形成知识闭环：

• 面试题 06. 从尾到头打印链表：反转思路的另一种应用（也可用栈/递归实现）；
• 面试题 18. 删除链表的节点：同样依赖「先暂存后继」的指针操作；
• 面试题 22. 链表中倒数第 k 个节点：双指针经典题，与反转链表共同构成链表指针操作基本功；
• 面试题 25. 合并两个排序的链表：递归思想在链表题中的又一次实战；
• 面试题 35. 复杂链表的复制 与 面试题 52. 两个链表的第一个公共节点：链表指针操作的进阶应用。

掌握「反转链表」这道题的两种解法，就等于掌握了链表指针操作的两大范式——迭代式的「头插/双指针」与递归式的「先拆后挂」，它们将反复出现在后续几乎所有链表类面试题中。

• 示例工程