SYSTEM
链表算法完整总结
src/content/notes/algorithm/链表.md 链表算法完整总结
刷题题目:206反转链表、141环形链表、142环形链表II、21合并两个有序链表、160相交链表
链表核心痛点:没有数组下标,只能靠next遍历;极易空指针;边界多(头节点、空链表、单节点);90%面试要求原地修改指针,不用数组存节点
四大通用模板(直接套)
模板1:反转链表 206
题型:整体反转链表、局部反转、k个一组反转的底层工具 思路:pre、cur双指针,逐个把节点next反向指向pre,不断向后移动。 易错细节
- pre初始
null,cur初始head - 先保存
temp = cur.next,再反转指针,防止链表断裂 - 最后
pre是新链表头,不是cur
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode temp = cur.next; // 暂存下一个节点
cur.next = pre; // 反转指向
pre = cur;
cur = temp;
}
return pre;
}
模板2:快慢指针(高频!141、142、19、234、876)
慢指针一次1步,快指针一次2步 适用题型
- 141:判断链表是否有环
- 142:有环,寻找环入口
- 876:找链表中点
- 19:删除倒数第N个节点(快先走n步)
①141 判断是否有环
思路:跑道赛跑,有环快指针一定会追上慢指针;无环快指针先跑到末尾null ⚠️关键细节(踩坑重点)
- while条件必须:
fast != null && fast.next != null - 只写
fast!=null会出现fast.next.next空指针 - 循环内部先移动指针,再判断是否相遇;不要一开始就判断,初始slow、fast都等于head会误判有环
- 有环返回true;跳出while代表到链表尾部返回false
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
②142 环形链表II,求环入口
思路
-
快慢指针先找相遇点;找不到相遇直接return null(这里极易漏,漏了直接空指针)
-
相遇后:slow挪回head,fast留在相遇点
-
两个指针
都每次走1步
,再次相遇节点就是环入口
⚠️注意:相遇点≠环入口!不要直接return slow
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
boolean hasCycle = false;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
hasCycle = true;
break;
}
}
if(!hasCycle) return null; //无环直接返回,避免后续fast=null空指针
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
模板3:虚拟头节点 dummy(21、19、24、25)
题型:合并链表、删除头节点、局部交换节点;当链表头部节点会被修改时必用dummy
dummy是我们new出来的假节点,不存业务数据,作用:统一所有节点处理逻辑,不用写大量if判断处理头节点特殊情况 ✅返回一定是
dummy.next;❌不能return dummy,会带上无效假节点
21 合并两个有序链表
思路
- 创建虚拟头
dummy,curr指针从dummy出发,用来拼接新链表 - while循环,两个链表都不为空,比较val,把小的节点接在
curr.next - curr向后移动
- 其中一个链表遍历结束,直接拼接剩下链表剩余部分
- 返回
dummy.next
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
curr.next = l1;
l1 = l1.next;
}else{
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 != null ? l1 : l2;
return dummy.next;
}
模板4:160相交链表
题型:找两个链表第一个公共交点 思路:指针A遍历完A链表就走B链表;指针B遍历完B链表就走A链表,相遇即为交点;都走到null代表不相交。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
while(pA != pB){
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
链表高频踩坑清单(今天全部踩过)
- 空指针NPE
- 执行
fast.next.next前,必须保证fast != null && fast.next != null - 无环场景,不要继续执行环入口逻辑,fast会变成null,访问.next直接报错
- 执行
- 虚拟头节点坑:返回
dummy.next,不要返回dummy - 快慢指针142坑:相遇点不是环入口,相遇后一个指针要重置回head,同速前进;必须先判断是否存在环
- 链表没有下标,不能
head[1],索引n代表向后走n次.next - 反转链表坑:一定要temp保存next,不然链表直接断裂;返回pre不是cur
- 循环条件不要写反;移动指针顺序不能颠倒(先移动再判断,还是先判断再移动)
后续刷题路线(母题变形)
- 19 删除链表倒数第N个节点(dummy+快慢指针)
- 234 回文链表(快慢找中点 + 复用206反转后半段)
- 2 两数相加(dummy+链表遍历)
- 24 两两交换链表节点
- 25 K个一组反转链表(链表综合天花板,集合反转+dummy+分段拼接)
- 148 排序链表(找中点+复用21合并有序链表)
做题通用流程(拿到链表题可以按这个步骤写)
- 先处理边界:head==null / head.next==null
- 判断是否需要
dummy(头节点会被修改就用) - 判断是否需要快慢指针(找环、找中点、倒数第n)
- 循环写条件,提前预判会不会出现null.next
- 指针移动顺序:保存next →修改指向 →移动指针
- 循环结束,处理剩余节点
- return正确的头节点,不要返回中间指针curr
面试链表题优先写原地O(1)空间解法,尽量不要用ArrayList存节点。