24. 两两交换链表中的节点给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。class Solution { public: // 方法虚拟头节点 迭代 ListNode* swapPairs(ListNode* head) { if(head NULL) return head; // 1. 创建虚拟头节点统一处理头节点交换 ListNode *dummy new ListNode(0); dummy-next head; // pre 指针指向【待交换两个节点的前一个节点】 ListNode *pre dummy; ListNode *cur, *next; // 定义两个待交换节点 // 循环条件后面至少有两个节点才能交换 while(pre-next pre-next-next) { // 定位三个关键节点 cur pre-next; // 第一个节点 next cur-next; // 第二个节点 // 核心三步交换 cur-next next-next; // 1. 第一个节点 指向 第三个节点 next-next cur; // 2. 第二个节点 指向 第一个节点 pre-next next; // 3. 前驱节点 指向 新的第一个节点 // pre 移动到下一组的前驱位置cur 已经变成后节点 pre cur; } return dummy-next; } };总结用了 dummy 虚拟头节点不用单独处理链表头部交换所有组逻辑统一。循环条件严谨pre-next pre-next-next保证剩下不足两个节点就停止不会空指针报错。空间复杂度 O (1)只操作指针不新建节点。19. 删除链表的倒数第 N 个结点给你一个链表删除链表的倒数第n个结点并且返回链表的头结点。class Solution { public: // 算法快慢指针快指针先走 N 步再一起走 ListNode* removeNthFromEnd(ListNode* head, int n) { // 快指针 p ListNode *p head; // 快指针先走 n 步 while(n--) p p-next; // 如果快指针走到空 → 要删的是【头节点】 if(!p) head head-next; else { // 慢指针 curpre 是前驱 ListNode *pre NULL; ListNode *cur head; // 一起走直到快指针到末尾 while(p){ p p-next; pre cur; cur cur-next; } // 前驱跳过 cur完成删除 pre-next cur-next; delete cur; } return head; } };总结1. 倒数第 N 个节点 正数第 len - N 1 个节点2. 快慢指针三步:快指针先走 n 步快慢一起走直到快指针到末尾此时慢指针正好指向倒数第 N 个节点面试题 02.07. 链表相交给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回null。class Solution { public: // 方法先求长度 → 对齐起点 → 同时遍历找交点 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *p1 headA; ListNode *p2 headB; int len1 0, len2 0; // 1. 计算链表A的长度 len1 while(p1){ len1; p1 p1-next; } // 2. 计算链表B的长度 len2 while(p2){ len2; p2 p2-next; } // 重置指针回到头部 p1 headA; p2 headB; // 3. 计算长度差让长链表先走 dif 步实现对齐 int dif len1 - len2; if(dif 0){ // A更长A先走 dif 步 while(dif--) p1 p1-next; } else { // B更长B先走 dif 步 dif -dif; while(dif--) p2 p2-next; } // 4. 两个指针【同时同速】向后走相等就是交点 while(p1 p2){ if(p1 p2) return p1; // 找到相交节点 p1 p1-next; p2 p2-next; } // 遍历完没找到 → 不相交 return NULL; } };总结1. 先对齐再同步走相遇就是交点算长度算出两个链表的长度差对齐长链表先走几步让两个指针在同一水平线找交点两个指针一起走地址相同就是交点2. 为什么判断p1 p2而不是值相等相交的定义是节点是同一个内存地址一样不是值相等就算相交142. 环形链表 II给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改 链表。class Solution { public: // 算法快慢指针 双指针找入口Floyd 判圈算法 ListNode *detectCycle(ListNode *head) { // 快慢指针都从头节点出发 ListNode *slow head; ListNode *fast head; // 第一步快慢指针往前走判断是否有环 // 快指针走两步慢指针走一步 while(fast fast-next) { slow slow-next; // 慢指针走 1 步 fast fast-next-next; // 快指针走 2 步 // 快慢指针相遇 → 说明有环 if(slow fast) { // 第二步一个指针从头走一个从相遇点走 // 速度相同再次相遇点就是【环入口】 ListNode *pre head; while(pre ! fast) { pre pre-next; fast fast-next; } // 找到环入口返回 return pre; } } // 循环退出 → 无环返回 NULL return NULL; } };总结1. 两步走快 2 慢 1相遇证明有环从链表头部和相遇点各出发一个指针每次都走 1 步最终一定会在环的入口相遇。2. 代码关键细节循环条件while(fast fast-next)快指针走两步必须保证fast和fast-next都不为空否则会报空指针错误。相遇后才找入口只有快慢指针相遇才能确定链表有环再执行入口查找逻辑。复杂度时间 O(n)空间 O(1)最优解法。链表章节总结一、常用方法1.虚拟头节点 dummy解决头节点需要删除 / 插入的麻烦让所有节点操作统一用到的题移除元素、两两交换、设计链表2.双指针快慢指针环形链表、删除倒数第 N 个前后指针反转链表、删除节点对齐指针相交链表二、核心思路1. 移除链表元素dummy 双指针找到就删pre 接上 cur 的下一个2. 设计链表dummy 维护头尾size 记录长度增删查改统一操作3. 反转链表保存 next → 反转指向 → 双指针后移4. 两两交换节点dummy 定位前驱三步交换指针pre 跳到下一组5. 删除倒数第 N 个快指针先走 N 步再一起走慢指针指向要删节点6. 相交链表算长度 → 长链表先走 → 对齐后一起走相遇即交点7. 环形链表 II最难快 2 慢 1 相遇证明有环头节点 相遇点同步走相遇即环入口三、模板1. 反转链表模板ListNode* reverseList(ListNode* head) { ListNode *pre NULL, *cur head; while(cur) { ListNode* tmp cur-next; cur-next pre; pre cur; cur tmp; } return pre; }2. 双指针删除 / 遍历模板dummy-next head; pre dummy, cur head; while(cur) { if(需要删除) { pre-next cur-next; delete cur; cur pre-next; } else { pre cur; cur cur-next; } }3. 快慢指针环 / 倒数第 N 个slow fast head; while(fast fast-next) { slow; fast 2; if(slow fast) ... }