链表常见手撕代码总结链表是面试中的高频考点本文整理了8道常见的链表手撕代码题目每道题包含题目描述、思路分析和Java代码实现。## 单链表节点定义javaclass ListNode { int val; ListNode next; ListNode(int x) { val x; next null; }}—## 1. 反转链表### 题目描述输入一个链表的头节点反转链表后输出新链表的头节点。示例- 输入1 - 2 - 3 - 4 - 5 - NULL- 输出5 - 4 - 3 - 2 - 1 - NULL### 思路描述使用三指针迭代法- 定义prev指向当前节点的前一个节点初始为null- 定义curr指向当前节点初始为head- 遍历过程中先用next保存下一个节点然后将curr.next指向prev完成反转- 然后prev和curr各向前移动一位- 当curr为null时prev就是新的头节点时间复杂度O(n)空间复杂度O(1)。### 代码实现javapublic ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 保存下一个节点 curr.next prev; // 反转指针 prev curr; // prev前移 curr next; // curr前移 } return prev; // prev就是新头节点}—## 2. 合并两个有序链表### 题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例- 输入1 - 2 - 41 - 3 - 4- 输出1 - 1 - 2 - 3 - 4 - 4### 思路描述使用虚拟头节点dummy技巧- 创建一个dummy节点作为新链表的虚拟头- 用curr指针指向新链表的当前末尾- 同时遍历两个链表比较当前节点值将较小的节点接到curr后面- 移动较小值对应的链表指针和curr指针- 当其中一个链表遍历完后直接将另一个链表剩余部分接上时间复杂度O(nm)空间复杂度O(1)。### 代码实现javapublic ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); 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;}—## 3. 链表中环的入口节点### 题目描述给定一个链表返回链表开始入环的第一个节点。如果链表无环则返回null。### 思路描述使用快慢指针Floyd判圈算法1.判断是否有环慢指针slow每次走一步快指针fast每次走两步。如果两指针相遇说明有环如果fast走到null说明无环。2.找环入口相遇后将其中一个指针重新移回头节点然后两个指针都每次走一步再次相遇的节点就是环的入口。数学证明设头节点到环入口距离为a环入口到相遇点距离为b相遇点到环入口距离为c。- 慢指针走了 a b- 快指针走了 a b c b a 2b c- 快指针速度是慢指针2倍2(a b) a 2b c → a c所以从头节点到环入口的距离 相遇点到环入口的距离。时间复杂度O(n)空间复杂度O(1)。### 代码实现javapublic ListNode detectCycle(ListNode head) { if (head null || head.next null) return null; 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 head; // fast重新回到起点 while (slow ! fast) { slow slow.next; fast fast.next; } return slow;}—## 4. 链表的中间节点### 题目描述给定一个头节点为head的非空单链表返回链表的中间节点。如果有两个中间节点则返回第二个中间节点。示例- 输入[1,2,3,4,5]- 输出节点3- 输入[1,2,3,4,5,6]- 输出节点4### 思路描述使用快慢指针- 慢指针slow每次走一步- 快指针fast每次走两步- 当fast走到链表末尾时slow正好在中间位置这种方法一次遍历即可找到中间节点不需要先统计链表长度。时间复杂度O(n)空间复杂度O(1)。### 代码实现javapublic ListNode middleNode(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow;}—## 5. 删除链表的倒数第N个节点### 题目描述给你一个链表删除链表的倒数第n个节点并且返回链表的头节点。进阶你能尝试使用一趟扫描实现吗### 思路描述使用快慢指针 虚拟头节点- 定义dummy节点简化删除头节点的边界情况- 快指针fast先向前走n1步- 然后快慢指针一起走保持n的距离- 当fast走到链表末尾null时slow正好在倒数第n1个节点的位置- 执行slow.next slow.next.next即可删除倒数第n个节点为什么要走n1步因为我们要找倒数第n个节点的前一个节点才能删除它。时间复杂度O(n)空间复杂度O(1)。### 代码实现javapublic ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode slow dummy; ListNode fast dummy; // fast先走n1步 for (int i 0; i n; i) { fast fast.next; } // 快慢一起走直到fast为null while (fast ! null) { slow slow.next; fast fast.next; } // 删除倒数第n个节点 slow.next slow.next.next; return dummy.next;}—## 6. 相交链表### 题目描述给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回null。### 思路描述使用双指针消除长度差- 指针pA从headA开始遍历遍历完A后接着遍历B- 指针pB从headB开始遍历遍历完B后接着遍历A- 如果两个链表相交pA和pB一定会在交点处相遇- 如果不相交两个指针最终都会变成null原理设A链表长度为acB链表长度为bcc是公共部分长度。- pA走的路径a c b- pB走的路径b c a- 两者路程相等所以一定会同时到达交点。时间复杂度O(nm)空间复杂度O(1)。### 代码实现javapublic ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA null || headB null) return null; ListNode pA headA; ListNode pB headB; while (pA ! pB) { pA (pA null) ? headB : pA.next; pB (pB null) ? headA : pB.next; } return pA;}—## 7. 回文链表### 题目描述给定一个链表的头节点head请你判断该链表是否为回文链表。如果是返回true否则返回false。### 思路描述结合快慢指针 反转链表1. 用快慢指针找到链表的中间节点2. 反转后半部分链表3. 分别从头节点和后半部分头节点开始逐一比较4. 如果所有节点值都相同则是回文链表5. 可选恢复链表结构这样可以实现O(n)时间复杂度和O(1)空间复杂度。时间复杂度O(n)空间复杂度O(1)。### 代码实现javapublic boolean isPalindrome(ListNode head) { if (head null || head.next null) return true; // 第一步找中间节点slow是中间或中间偏左 ListNode slow head; ListNode fast head; while (fast.next ! null fast.next.next ! null) { slow slow.next; fast fast.next.next; } // 第二步反转后半部分 ListNode secondHalf reverseList(slow.next); slow.next null; // 断开前后两部分 // 第三步比较两部分 ListNode p1 head; ListNode p2 secondHalf; boolean result true; while (p2 ! null) { if (p1.val ! p2.val) { result false; break; } p1 p1.next; p2 p2.next; } // 可选恢复链表 // slow.next reverseList(secondHalf); return result;}// 复用反转链表方法private ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } return prev;}—## 8. 两两交换链表中的节点### 题目描述给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。示例- 输入1 - 2 - 3 - 4- 输出2 - 1 - 4 - 3### 思路描述使用虚拟头节点 迭代- 定义dummy节点指向head- 用curr指针从dummy开始每次处理两个节点- 关键步骤 1. 保存第一个节点node1 curr.next2. 保存第二个节点node2 curr.next.next3. 反转node1.next node2.nextnode1指向后面还未处理的部分 4.node2.next node1node2指向node1 5.curr.next node2curr指向node2 6.curr node1curr移动到下一组的前一个位置时间复杂度O(n)空间复杂度O(1)。### 代码实现javapublic ListNode swapPairs(ListNode head) { ListNode dummy new ListNode(0); dummy.next head; ListNode curr dummy; while (curr.next ! null curr.next.next ! null) { ListNode node1 curr.next; ListNode node2 curr.next.next; // 交换 node1.next node2.next; node2.next node1; curr.next node2; // curr移动到下一组的前一个位置 curr node1; } return dummy.next;}—## 总结| 题目 | 核心技巧 | 时间复杂度 | 空间复杂度 ||------|---------|-----------|-----------|| 反转链表 | 三指针迭代 | O(n) | O(1) || 合并两个有序链表 | 虚拟头节点 | O(nm) | O(1) || 环的入口节点 | 快慢指针(Floyd) | O(n) | O(1) || 中间节点 | 快慢指针 | O(n) | O(1) || 删除倒数第N个节点 | 快慢指针 dummy | O(n) | O(1) || 相交链表 | 双指针消除长度差 | O(nm) | O(1) || 回文链表 | 快慢指针 反转 | O(n) | O(1) || 两两交换节点 | dummy 迭代 | O(n) | O(1) |**链表解题核心技巧总结**1.虚拟头节点dummy简化头节点变更的边界处理2.快慢指针找中间节点、判断环、找倒数第k个节点3.哨兵/多指针同时维护多个指针处理复杂逻辑4.画图链表题一定要画图指针操作一目了然以上就是链表面试中最常考的手撕代码题目建议大家手动敲几遍彻底掌握指针操作的细节。