一.单链表

基础概念类提问单链表和数组最核心的区别是什么各自适合什么场景回答核心差异就四点内存布局数组连续链表零散不连续访问效率数组支持随机访问按下标找元素 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。快指针走了abcb慢指针走了ab快是慢的 2 倍算下来ac所以同步走一定会在入口相遇。时间 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 (nm)空间 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; }