企业官网建设流程全解析

链表常见手撕代码总结

链表是面试中的高频考点，本文整理了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 -> 4，1 -> 3 -> 4- 输出：1 -> 1 -> 2 -> 3 -> 4 -> 4### 思路描述使用虚拟头节点（dummy）技巧：- 创建一个dummy节点，作为新链表的虚拟头- 用curr指针指向新链表的当前末尾- 同时遍历两个链表，比较当前节点值，将较小的节点接到curr后面- 移动较小值对应的链表指针和curr指针- 当其中一个链表遍历完后，直接将另一个链表剩余部分接上时间复杂度O(n+m)，空间复杂度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先向前走n+1步- 然后快慢指针一起走，保持n的距离- 当fast走到链表末尾（null）时，slow正好在倒数第n+1个节点的位置- 执行slow.next = slow.next.next即可删除倒数第n个节点为什么要走n+1步？因为我们要找倒数第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先走n+1步 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链表长度为a+c，B链表长度为b+c（c是公共部分长度）。- pA走的路径：a + c + b- pB走的路径：b + c + a- 两者路程相等，所以一定会同时到达交点。时间复杂度O(n+m)，空间复杂度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.next（node1指向后面还未处理的部分） 4.node2.next = node1（node2指向node1） 5.curr.next = node2（curr指向node2） 6.curr = node1（curr移动到下一组的前一个位置）时间复杂度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(n+m) | O(1) || 环的入口节点 | 快慢指针(Floyd) | O(n) | O(1) || 中间节点 | 快慢指针 | O(n) | O(1) || 删除倒数第N个节点 | 快慢指针 + dummy | O(n) | O(1) || 相交链表 | 双指针消除长度差 | O(n+m) | O(1) || 回文链表 | 快慢指针 + 反转 | O(n) | O(1) || 两两交换节点 | dummy + 迭代 | O(n) | O(1) |**链表解题核心技巧总结：**1.虚拟头节点（dummy）：简化头节点变更的边界处理2.快慢指针：找中间节点、判断环、找倒数第k个节点3.哨兵/多指针：同时维护多个指针处理复杂逻辑4.画图：链表题一定要画图，指针操作一目了然以上就是链表面试中最常考的手撕代码题目，建议大家手动敲几遍，彻底掌握指针操作的细节。