最近重新准备 C/C++ 面试，发现自己虽然做了很多业务开发，但基础数据结构已经生疏了不少。因此决定从 LeetCode 最经典的链表题开始系统复习。

本文记录了我完成的四道高频链表题，以及过程中总结出的核心套路。

一、链表基础知识
链表节点定义

LeetCode 中最常见的定义：

struct ListNode
{
int val;
ListNode* next;

ListNode(int x)
{
    val = x;
    next = NULL;
}

};

每个节点包含：

val -> 当前节点数据
next -> 指向下一个节点

例如：

1 -> 2 -> 3 -> NULL

内存关系：

±----±----+ ±----±----+ ±----±-----+
| 1 | *-------> | 2 | *-------> | 3 | NULL |
±----±----+ ±----±----+ ±----±-----+
二、必须掌握的指针知识
对象访问成员
ListNode node(1);

node.val = 1;
node.next = NULL;

使用：

.
指针访问成员
ListNode* p = &node;

p->val = 1;
p->next = NULL;

使用：

->
两种写法区别
栈对象
ListNode dummy(0);

访问：

dummy.next
堆对象
ListNode* dummy = new ListNode(0);

访问：

dummy->next
三、LeetCode 206：反转链表
题目
1 -> 2 -> 3 -> 4 -> 5

变为

5 -> 4 -> 3 -> 2 -> 1
核心思想

反转过程实际上是在不断修改：

curr->next

原来：

1 -> 2

变成：

2 -> 1
三指针法

需要保存：

prev
curr
next

否则链表会断掉。

动态过程

初始：

prev = NULL
curr = 1

第一轮：

next = curr->next;
curr->next = prev;

结果：

1 -> NULL

curr = 2
prev = 1

第二轮：

2 -> 1 -> NULL

最终：

5 -> 4 -> 3 -> 2 -> 1 -> NULL
代码
ListNode* reverseList(ListNode* head)
{
ListNode* prev = NULL;
ListNode* curr = head;

while(curr)
{
    ListNode* next = curr->next;

    curr->next = prev;

    prev = curr;
    curr = next;
}

return prev;

}
复杂度

时间复杂度：

O(n)

每个节点访问一次。

空间复杂度：

O(1)

只使用了三个辅助指针。

四、LeetCode 21：合并两个有序链表
题目
1 -> 2 -> 4

1 -> 3 -> 4

合并后：

1 -> 1 -> 2 -> 3 -> 4 -> 4
核心思想

类似归并排序中的 merge。

每次比较：

list1->val
list2->val

谁小接谁。

Dummy Node（虚拟头节点）

经典写法：

ListNode dummy(0);
ListNode* curr = &dummy;

作用：

避免头节点特殊处理
统一插入逻辑
代码
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
ListNode dummy(0);

ListNode* curr = &dummy;

while(list1 && list2)
{
    if(list1->val < list2->val)
    {
        curr->next = list1;
        list1 = list1->next;
    }
    else
    {
        curr->next = list2;
        list2 = list2->next;
    }

    curr = curr->next;
}

curr->next = list1 ? list1 : list2;

return dummy.next;

}
为什么没有创建新节点？

因为直接复用了原链表节点：

curr->next = list1;

只是修改了：

next指针指向

而没有：

new ListNode(…)
复杂度

时间：

O(m+n)

空间：

O(1)
五、LeetCode 141：环形链表
题目

判断链表是否有环。

例如：

1 -> 2 -> 3
^ |
|____|
快慢指针

定义：

slow
fast

速度：

slow = slow->next;
fast = fast->next->next;
为什么能相遇？

假设链表有环：

1 -> 2 -> 3 -> 4
^ |
|_______|

快指针每次比慢指针多走一步。

进入环后：

距离不断缩小

最终必然相遇。

代码
bool hasCycle(ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head;

while(fast && fast->next)
{
    slow = slow->next;
    fast = fast->next->next;

    if(slow == fast)
    {
        return true;
    }
}

return false;

}
复杂度

时间：

O(n)

空间：

O(1)
六、LeetCode 19：删除链表倒数第 N 个节点
题目
1 -> 2 -> 3 -> 4 -> 5

n = 2

删除后：

1 -> 2 -> 3 -> 5
核心难点

删除节点时需要找到：

目标节点前一个节点

因为链表删除本质是：

prev->next = prev->next->next;
Dummy + 快慢指针

构造：

ListNode dummy(0);

dummy.next = head;

定义：

slow = &dummy
fast = &dummy

先让 fast 走：

n + 1

步。

然后：

slow
fast

同步前进。

当：

fast == NULL

时：

slow

刚好停在待删除节点前一个位置。

代码
ListNode* removeNthFromEnd(ListNode* head, int n)
{
ListNode dummy(0);

dummy.next = head;

ListNode* slow = &dummy;
ListNode* fast = &dummy;

for(int i = 0; i < n + 1; i++)
{
    fast = fast->next;
}

while(fast)
{
    slow = slow->next;
    fast = fast->next;
}

slow->next = slow->next->next;

return dummy.next;

}
复杂度

时间：

O(n)

空间：

O(1)
七、链表面试核心套路总结

经过这几题，可以总结出链表面试最重要的四个套路：

题目 核心套路
206 反转链表 prev + curr + next
21 合并有序链表 dummy + tail
141 环形链表 fast + slow
19 删除倒数第N个 dummy + fast/slow
八、复杂度分析经验

很多面试者容易混淆时间复杂度和空间复杂度。

时间复杂度

关注：

循环执行次数

例如：

while(curr)

遍历整个链表：

O(n)
空间复杂度

关注：

是否额外申请空间

例如：

ListNode* prev;
ListNode* curr;
ListNode* next;

只有固定数量变量：

O(1)

如果：

new ListNode(…)

随着 n 增长不断创建节点：

O(n)
结语

链表看起来简单，但几乎覆盖了 C/C++ 面试中的核心基础：

指针
内存模型
结构体与类
Dummy Node
快慢指针
时间复杂度分析
空间复杂度分析

如果能够熟练掌握 206、21、141、19 这四题，已经具备了应对大部分链表面试题的基础能力。

下一阶段我准备继续学习：

LeetCode 20 有效括号（栈）
LeetCode 232 用栈实现队列
LeetCode 104 二叉树最大深度
LeetCode 226 翻转二叉树

逐步补齐数据结构与算法基础。