一.单链表-拓冰建站

基础概念类

提问：单链表和数组最核心的区别是什么？各自适合什么场景？

回答：

核心差异就四点：
内存布局：数组连续，链表零散不连续
访问效率：数组支持随机访问，按下标找元素 O (1)；链表只能从头顺着摸，查找 O (n)
增删效率：数组中间插入 / 删除要挪动后面所有元素，O (n)；链表只要找到目标位置，改两个指针就完事，O (1)
扩容成本：数组满了要重新申请一大块连续内存，再把旧数据全拷贝过去；链表随用随申请节点，几乎零扩容成本

数组理解成「电影院里连续的一排座位」，内存是连续的；单链表就是「寻宝游戏的线索链」，每个节点藏着下一个节点的地址，内存是零散的。

适用场景：频繁随机查找用数组；频繁插入删除、数据量不确定的场景用链表。

核心算法类

1. 怎么反转一个单链表？

提问：写一下单链表反转，分别说下迭代和递归的思路。

回答：

迭代法（最优，优先写）
用三个指针：prev（前一个节点）、curr（当前节点）、next（存下一个节点防止断链）。
从头遍历，每次把curr->next指向prev，然后三个指针整体往后挪一步，直到curr为空，prev就是新的头节点。
时间 O (n)，空间 O (1)，原地反转。

递归法
先一路递归到链表最后一个节点（它就是反转后的新头），然后回溯的时候，把当前节点的next->next指向自己，再把自己的next置空，相当于从后往前逐个翻指针。
时间 O (n)，空间 O (n)（递归调用栈）。

边界：空链表、只有 1 个节点的情况，直接返回头节点就行，不用处理。

2. 如何判断单链表有没有环？怎么找环的入口？

提问：不用额外空间，怎么判断链表有环？

回答：

用「龟兔赛跑」的思路：一个慢指针每次走 1 步，一个快指针每次走 2 步，同时从头出发。
如果链表没环，快指针一定会先走到尾节点（遇到 null）；
如果有环，快指针一定会在环里追上慢指针，两者相遇就说明有环。

找环入口（延伸考点）：
相遇之后，把其中一个指针放回链表头部，两个指针都改成每次走 1 步，再次相遇的位置就是环的入口。
原理很简单：假设头到入口距离是 a，入口到相遇点是 b，相遇点回入口是 c。快指针走了a+b+c+b，慢指针走了a+b，快是慢的 2 倍，算下来a=c，所以同步走一定会在入口相遇。
时间 O (n)，空间 O (1)，是最优解。

3. 怎么一次遍历找到链表的中间节点？

提问：不先遍历计数，怎么找中间节点？

回答：

还是快慢指针的思路：两个人一起出发，快的速度是慢的 2 倍，快的走到终点的时候，慢的刚好走到一半。
快指针每次走 2 步，慢指针每次走 1 步，快指针走到尾节点时，慢指针指向的就是中间节点。
节点数是奇数：慢指针刚好在正中间；
节点数是偶数：一般返回第二个中间节点（看题目要求，调整终止条件就行）。
比「先数长度再走一半」更优雅，虽然时间都是 O (n)，但只遍历一次，空间 O (1)。

4. 删除链表倒数第 N 个节点，怎么一次遍历完成？

提问：不能先算总长度，怎么一次遍历删掉倒数第 N 个节点？

回答：

还是快慢指针的技巧：让快指针先走 N 步，然后快慢指针一起往前走，快指针走到链表末尾的时候，慢指针刚好站在「倒数第 N 个节点的前一个节点」，直接删掉慢指针的 next 就行。
必提边界细节：一定要加一个哑节点（dummy）连在头节点前面。不然要删除的刚好是头节点的时候，慢指针就没地方站了，哑节点能统一所有情况的处理逻辑。
时间 O (n)，空间 O (1)。

5. 合并两个有序单链表，保持整体有序？

提问：合并两个升序链表，输出还是升序。

回答：

类比成「两列按身高排好的队伍，每次挑两个队头里更矮的人，依次拼成新队伍」。
迭代法（推荐）：
先建一个哑节点当新链表的队头，用两个指针分别遍历两个链表，每次把值更小的节点接到新链表后面，对应指针后移，直到其中一个链表走完，把剩下没走完的直接接在尾部。
时间 O (n+m)，空间 O (1)。
递归法：
谁的值小，谁就当当前的头节点，然后让它的 next 指向「剩下两个链表递归合并的结果」。代码更短，但有递归栈空间开销。

进阶理解类

提问：单链表有什么天生的缺陷？工程上有哪些优化方向？

回答：

单链表的核心缺陷有：
只能单向遍历，想找前一个节点必须从头再来，尾部删除效率极低；
不能随机访问，查找必须 O (n)；
节点自带指针开销，而且内存不连续，CPU 缓存命中率很低，比数组慢很多。

工程上常见的优化方向：
加一个前驱指针，变成双向链表，解决反向遍历和尾删问题，比如 Linux 内核链表、LRU 缓存都用双向链表；
给链表加多层索引，变成跳表，把查找效率从 O (n) 降到 O (logn)，Redis 的有序集合就是这么实现的；
首尾相连做成循环链表，适合环形队列、约瑟夫环这类场景。

提问：为什么 LRU 缓存、操作系统就绪队列都偏爱链表，不用数组？

回答：

核心原因是这些场景高频做节点的移动、插入、删除。
比如 LRU 缓存，每次访问一个元素，都要把它移到链表最前面；缓存满了，要删掉链表最后面的元素。链表只要改两个指针就能完成，O (1) 搞定。
如果用数组，每次移动元素都要批量挪动数据，O (n) 的开销，在高频场景下性能差很多。

代码练习

链表节点

struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {}; }

反转单链表

考点：指针操作、原地算法、边界处理

ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while(curr != nullptr) { ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }

判断链表是否有环

考点：快慢指针思想、空指针边界

bool hasCycle(ListNode* head) { if(head == nullptr) return false; ListNode* slow = head; ListNode* fast = head; while(fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false; }

提醒：循环条件必须同时判断fast和fast->next非空，否则fast->next->next会触发空指针崩溃。

找环的入口节点(高频)

ListNode* detectCycle(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while(fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if(slow == fast) { slow = head; while(slow != fast) { slow = slow->next; fast = fast->next; } return slow; } } return nullptr; }

一次遍历找链表中间节点

考点：快慢指针技巧

ListNode* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while(fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; }

提醒：偶数个节点时，返回第二个中间节点；如果题目要求返回第一个，把循环条件改成fast->next && fast->next->next即可。

一次遍历删除倒数第 N 个节点

考点：快慢指针、哑节点技巧

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new Listnode(0); dummy->next = head; ListNode* slow = dummy; ListNode* fast = dummy; for(int i = 0; i < n; i ++ ) fast = fast->next; while(fast->next != nullptr) { slow = slow->next; fast = fast->next; } ListNode* delNode = slow->next; slow->next = slow->next->next; delete delNode; ListNode* res = dummy->next; delete dummy; return res; }