【LeetCode 热题 100】（七）链表

160. 相交链表

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}

解题思路：双指针路径补偿法（寻找链表交点）

核心思想：消除长度差实现同步遍历

巧妙的路径补偿机制：
通过让两个指针遍历"组合路径"（链表A + 链表B），自动消除两链表的长度差异，使指针能在交点或终点同步相遇。

关键步骤解析：

1. 边界条件处理：

   if (headA == null || headB == null) {return null;
   }
   

   • 任一链表为空时直接返回null（不可能存在交点）

2. 双指针初始化：

   ListNode pA = headA, pB = headB;
   

   • pA 从链表A头节点出发
   • pB 从链表B头节点出发

3. 路径补偿遍历：

   while (pA != pB) {pA = (pA == null) ? headB : pA.next;pB = (pB == null) ? headA : pB.next;
   }
   

   • 核心操作：
     • 当 pA 走到A链表尾部时，跳转到B链表头部
     • 当 pB 走到B链表尾部时，跳转到A链表头部
   • 路径补偿原理：
     • 每个指针都走完整个组合路径（A链表 + B链表）
     • 路径总长度 = 链表A长度(a) + 链表B长度(b)

数学证明：

设：

• 链表A独有长度：a
• 链表B独有长度：b
• 公共部分长度：c（若无交点则c=0）

场景	pA路径	pB路径	相遇点
有交点	a + (b + c)	b + (a + c)	交点处
无交点	a + b	b + a	null

执行流程示例：

有交点情况：

链表A：1→2→3→4→5
链表B：   9→4→5   (交点为4)遍历路径：
pA路径：1→2→3→4→5→9→4 (相遇点)
pB路径：9→4→5→1→2→3→4 (相遇点)
步数：  1 2 3 4 5 6 7

无交点情况：

链表A：1→2→3→null
链表B：4→5→6→null遍历路径：
pA路径：1→2→3→4→5→6→null
pB路径：4→5→6→1→2→3→null↑ 相遇点（都是null）

算法特性：

1. 自动长度补偿：
   无需计算链表长度，路径交换自动处理长度差异

2. 时间复杂度：O(m+n)
   m和n为链表长度，每个指针最多遍历m+n个节点

3. 空间复杂度：O(1)
   仅使用两个指针，常数级空间

4. 边界处理完善：

   • 处理单链表（a=0或b=0）
   • 处理完全重叠链表（a=0且b=0）
   • 处理不相交链表

为什么能正确工作？

路径等长原理：
无论是否存在交点，两指针最终都会走过相同的路径长度：

• 有交点：路径长度 = a + b + c
• 无交点：路径长度 = a + b

在第二轮遍历中，两指针会同时进入对方的链表区域，最终在交点或终点（null）相遇。

复杂度分析：

维度	结果	说明
时间复杂度	O(m+n)	最坏情况遍历两链表各一次
空间复杂度	O(1)	仅用两个指针
链表修改	无	只读操作

这种解法通过巧妙的路径补偿机制，在不使用额外空间、不修改链表结构的前提下，高效解决了链表交点检测问题，是链表问题中双指针技巧的经典应用。

206. 反转链表

class Solution {public ListNode reverseList(ListNode head) {if(head == null){return null;}ListNode current = head;ListNode prev = null;while(current!=null){ListNode nextTemp = current.next;current.next = prev;  prev = current;       current = nextTemp;  }return prev; }
}

解题思路：迭代法反转链表

核心思想：三指针原地反转

使用三个指针动态修改节点指向，实现链表原地反转：

1. prev：指向已反转部分链表的头节点
2. current：指向当前待处理节点
3. nextTemp：临时保存下一个待处理节点

关键步骤解析：

1. 边界处理：

   if (head == null) return null;
   

   • 处理空链表特殊情况

2. 指针初始化：

   ListNode current = head;  // 当前操作节点（初始为头节点）
   ListNode prev = null;     // 已反转部分的头节点（初始为空）
   

3. 迭代反转过程：

   while (current != null) {// 1. 保存下一个节点（防止丢失）ListNode nextTemp = current.next;// 2. 反转指针：当前节点指向已反转部分current.next = prev;// 3. 移动指针：已反转部分前移prev = current;// 4. 移动指针：当前节点前移current = nextTemp;
   }
   

   • 四步操作不可分割：
     1. 保存后续节点（关键！避免链表断裂）
     2. 反转当前节点指针
     3. 更新已反转链表头
     4. 移动到下一个待处理节点

4. 返回结果：

   return prev;  // 循环结束时prev指向新链表头节点
   

执行过程示例（反转 1→2→3→null）：

循环	current	prev	nextTemp	链表状态	说明
初始	1	null	-	1→2→3→null	初始状态
1	1	null	2	1→null	当前节点指向prev
		→1		2→3→null	prev移动到当前节点
	→2				current移动到nextTemp
2	2	1	3	2→1→null	当前节点指向prev
		→2		3→null	prev移动到当前节点
	→3				current移动到nextTemp
3	3	2	null	3→2→1→null	当前节点指向prev
		→3			prev移动到当前节点
	→null				current移动到nextTemp
结束	返回 prev=3			3→2→1→null	新链表头节点

算法特性：

1. 原地操作：

   • 直接在原链表上修改指针，空间复杂度 O(1)
   • 不需要额外创建链表节点

2. 时间复杂度：

   • 单次遍历完成反转，时间复杂度 O(n)
   • 每个节点仅访问一次

3. 指针移动逻辑：

   • prev 始终指向已反转部分的头节点
   • current 始终指向待反转部分的头节点
   • nextTemp 保证链表不断裂的关键

关键技巧：

• 断链前保存：修改指针前必须保存 current.next
• 指针移动顺序：
  1. 保存后续节点
  2. 反转当前指针
  3. 更新prev
  4. 更新current
• 终止条件：current == null 时完成反转

复杂度分析：

维度	结果	说明
时间复杂度	O(n)	单次遍历链表
空间复杂度	O(1)	仅用三个指针
链表修改	原地	不创建新节点

这种迭代法是链表反转的最优解法，通过巧妙的指针操作实现高效反转，是处理链表问题的核心基础操作。

234. 回文链表

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if(head==null){return true;}ListNode middle =  middle_node(head);ListNode reverse1 = reverse(middle.next);ListNode pA = head;ListNode pB = reverse1;while(pA!=null && pB!=null){if(pA.val != pB.val){return false;}pA = pA.next;pB = pB.next;}ListNode reverse2 = reverse(middle.next);middle.next = reverse2;return true;}// 1.中间结点private ListNode middle_node(ListNode head){ListNode slow = head, fast = head;while(fast.next!=null && fast.next.next!=null){fast = fast.next.next;slow = slow.next;}return slow;}private ListNode reverse(ListNode head){ListNode pre = null;ListNode current = head;while(current!=null){ListNode nextNode = current.next;current.next = pre;pre = current;current = nextNode;}return pre;}}

解题思路描述

这段代码通过以下步骤判断链表是否为回文链表：

1. 边界处理

   • 如果链表为空（head == null），直接返回 true（空链表视为回文）

2. 寻找前半部分尾节点

   • 使用快慢指针法找到链表前半部分的尾节点
   • 快指针每次移动两步，慢指针每次移动一步
   • 当快指针到达链表末尾时，慢指针指向：
     • 奇数链表：中间节点的前一个节点（如 1->2->3 中指向 2）
     • 偶数链表：前半部分尾节点（如 1->2->3->4 中指向 2）

3. 反转后半部分链表

   • 将前半部分尾节点的下一个节点作为后半部分头节点
   • 通过迭代法反转后半部分链表
   • 示例：3->4->5 反转为 5->4->3

4. 比较前后两部分

   • 使用双指针同步遍历：
     • pA 从头节点开始（前半部分）
     • pB 从反转后的头节点开始（后半部分）
   • 逐个比较节点值：
     • 发现不同值立即返回 false
     • 全部相同则继续比较

5. 恢复链表结构（可选但推荐）

   • 将反转的后半部分再次反转恢复原顺序
   • 重新连接到前半部分尾节点
   • 目的：保持输入链表的原始结构

6. 返回结果

   • 所有节点值匹配时返回 true

关键点说明

• 快慢指针终止条件：fast.next != null && fast.next.next != null
  • 确保慢指针精确停在前半部分尾节点
• 奇数链表处理：中间节点不参与比较
  • 示例：1->2->3 只比较 1 和 3
• 时间复杂度 O(n)：包含三次线性遍历
  • 找中点（n/2）
  • 反转后半部分（n/2）
  • 比较节点（n/2）
• 空间复杂度 O(1)：仅使用指针变量

示例演示

输入链表：1 -> 2 -> 3 -> 2 -> 1

1. 快慢指针停止在节点3（前半部分尾节点）
2. 反转后半部分：2->1 变为 1->2
3. 比较：
   • pA=1 vs pB=1 → 相同
   • pA=2 vs pB=2 → 相同
4. 恢复后半部分：1->2 反转回 2->1
5. 返回 true

此解法高效处理了回文链表的检测，同时保持链表原始结构，是面试中的理想解决方案。

141. 环形链表

public class Solution {public boolean hasCycle(ListNode head) {HashSet<ListNode> nodeSet =  new HashSet<>();if(head==null || head.next==null){return false;}ListNode current = head;while(current!=null){if(nodeSet.contains(current)){return true;}nodeSet.add(current);current = current.next;}return false;}
}

解题思路描述

这段代码通过哈希集合检测法判断链表是否有环，思路清晰且易于理解：

---

核心思想

利用哈希集合记录访问过的节点，当遇到重复节点时说明存在环。

---

关键步骤

1. 边界处理（特殊链表直接判断）：

   • 空链表（head == null）→ 无环
   • 单节点链表（head.next == null）→ 无环

2. 初始化工具：

   • 创建哈希集合 nodeSet（记录已访问节点）
   • 指针 current 从链表头开始移动

3. 遍历检测（核心逻辑）：

   graph LR
   A[开始遍历] --> B{当前节点是否在集合中？}
   B -- 是 --> C[发现环 → 返回 true]
   B -- 否 --> D[节点加入集合]
   D --> E[移动到下一节点]
   E --> F{是否到链表末尾？}
   F -- 是 --> G[无环 → 返回 false]
   F -- 否 --> B
   

4. 终止条件：

   • 发现重复节点 → 立即返回 true（有环）
   • 遍历到链表末尾（current == null）→ 返回 false（无环）

---

复杂度分析

维度	说明
时间复杂度	O(n) 每个节点仅访问一次
空间复杂度	O(n) 最坏情况存储所有节点

---

示例演示

有环链表：A → B → C → D → B（D指向B形成环）

1. 访问 A → 加入集合 {A}
2. 访问 B → 加入集合 {A,B}
3. 访问 C → 加入集合 {A,B,C}
4. 访问 D → 加入集合 {A,B,C,D}
5. 再次访问 B → 在集合中找到 → 返回 true

无环链表：A → B → C → D → null

1. 依次访问 A/B/C/D 加入集合
2. 访问 null → 返回 false

---

方法特点

• 优点：逻辑简单直接，适用于面试快速实现
• 缺点：需要额外空间存储节点
• 替代方案：快慢指针法（空间复杂度 O(1)，但逻辑稍复杂）

此解法是检测链表环的经典方法之一，清晰体现了哈希集合在重复性检测中的应用价值。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(head==null || head.next==null){return false;}ListNode slow = head;ListNode fast = head.next;while(slow!=fast){if(fast==null||fast.next==null){return false;}fast = fast.next.next;slow = slow.next;}return true;}
}

解题思路描述：快慢指针法（Floyd 判圈算法）

核心思想

利用两个指针以不同速度遍历链表：

• 慢指针：每次移动 1 个节点
• 快指针：每次移动 2 个节点
  若有环，快指针最终会追上慢指针（相遇）；若无环，快指针会先到达链表尾部。

---

关键步骤

1. 边界处理：

   • 链表为空或只有一个节点 → 直接返回 false（不可能有环）

2. 指针初始化：

   • slow 指向头节点 head
   • fast 指向 head.next（错位初始化确保首次比较有效）

3. 循环检测：

   graph TB
   A[开始循环] --> B{slow ≠ fast?}
   B -- 是 --> C{fast是否到链表尾?}
   C -- 是 --> D[返回false]
   C -- 否 --> E[slow移动1步]
   E --> F[fast移动2步]
   F --> B
   B -- 否 --> G[返回true]
   

4. 终止条件：

   • 有环：slow == fast（两指针相遇）→ 返回 true
   • 无环：fast 遇到 null → 返回 false

---

算法原理

• 有环情况：快指针每次比慢指针多走 1 步，相当于快指针以相对速度 1 节点/次追赶
  • 设环长度为 L，最多经过 L 次移动后必然相遇
• 无环情况：快指针将率先到达链表末尾（null）

---

复杂度分析

维度	说明
时间复杂度	O(n) 最坏情况遍历整个链表
空间复杂度	O(1) 仅使用两个指针

---

示例演示

有环链表（1→2→3→4→2）：

初始: slow=1, fast=2
第1轮: slow=2, fast=4  (1≠2)
第2轮: slow=3, fast=3  (2≠4 → 移动后相遇)
返回 true

无环链表（1→2→3→4）：

初始: slow=1, fast=2
第1轮: slow=2, fast=4  (1≠2)
第2轮: fast=null → 返回 false

---

方法特点

• 空间最优：无需额外存储空间（哈希表法需要 O(n) 空间）
• 高效可靠：数学证明必然能在环内相遇
• 经典应用：除检测环外，还可用于寻找环入口（相遇后重置指针）

此解法是检测链表环的最优方法之一，由计算机科学家 Robert W. Floyd 提出，故称 Floyd Cycle Detection Algorithm。

142. 环形链表2

解题思路

这段代码实现了检测链表中环的入口节点，采用经典的快慢指针（Floyd 判圈算法），分为两个关键阶段：

1. 判断链表是否有环：

   • 初始化两个指针 slow 和 fast，均指向链表头节点 head。
   • slow 每次移动 1 步，fast 每次移动 2 步。
   • 若 fast 遇到 null（或 fast.next 为 null），说明链表无环，返回 null。
   • 当 slow 和 fast 相遇时，说明链表有环，进入下一阶段。

2. 寻找环的入口节点：

   • 将其中一个指针（如 slow）保持在相遇点，另一个指针 ptr 重新指向头节点 head。
   • ptr 和 slow 同时每次移动 1 步，直到它们相遇。
   • 相遇点即为环的入口节点。

正确性证明

设：

• 头节点到环入口距离为 a。
• 环入口到相遇点距离为 b。
• 相遇点到环入口距离为 c（环长 = b + c）。
• 相遇时，slow 走了 a + b 步，fast 走了 a + b + k(b + c) 步（k 为快指针绕环圈数）。
• 因快指针速度是慢指针的 2 倍：
  2(a + b) = a + b + k(b + c)
  化简得：a = (k - 1)(b + c) + c。
• 该式表明：头节点到环入口的距离 a 等于 从相遇点走 c 步加上 (k-1) 圈环长。因此两指针同步移动必在环入口相遇。

代码解析

public class Solution {public ListNode detectCycle(ListNode head) {if (head == null) return null; // 空链表直接返回ListNode slow = head, fast = head;while (fast != null) {slow = slow.next;          // 慢指针走1步if (fast.next != null) {fast = fast.next.next; // 快指针走2步} else {return null;           // 无环}if (fast == slow) {        // 首次相遇ListNode ptr = head;while (ptr != slow) {  // 同步移动找入口ptr = ptr.next;slow = slow.next;}return ptr;            // 环入口}}return null; // 遍历结束无环}
}

复杂度分析

• 时间复杂度：O(n)
  • 阶段 1：最坏情况下遍历整个链表（n 为节点数）。
  • 阶段 2：最坏遍历 a（入口距离）次。
• 空间复杂度：O(1)
  仅使用固定数量的指针，无额外空间开销。

示例
链表 3 → 2 → 0 → -4（-4 指向 2）：

1. slow 和 fast 在 -4 和 2 之间的某点相遇（如 0）。
2. ptr 从 3 出发，slow 从 0 出发，同步移动后在环入口 2 相遇。

21. 合并两个有序链表

解题思路：合并两个有序链表

核心思想：使用双指针遍历两个链表，通过比较节点值逐个合并，最终生成一个新的有序链表。整个过程类似于归并排序中的合并步骤。

关键步骤：

1. 创建虚拟头节点（哑节点）

   • 作用：避免处理空链表的情况，简化头节点操作
   • 初始化：ListNode head = new ListNode(-1)
   • 维护指针ptr始终指向新链表的末尾

2. 双指针遍历比较

   • 指针p1遍历list1，p2遍历list2
   • 比较当前节点值：
     • 若p1.val <= p2.val：将p1接入新链表，p1后移
     • 否则：将p2接入新链表，p2后移
   • 每次操作后：新链表指针ptr后移

3. 处理剩余节点

   • 当某个链表遍历完时，将另一链表的剩余部分直接接入新链表
   • 利用三元运算符：ptr.next = (p1 == null) ? p2 : p1

4. 返回结果

   • 实际头节点是虚拟头节点的下一节点：return head.next

执行过程示例：

List1: 1 → 3 → 5
List2: 2 → 4 → 6步骤1：1 < 2 → 新链表: -1 → 1
步骤2：3 > 2 → 新链表: -1 → 1 → 2
步骤3：3 < 4 → 新链表: -1 → 1 → 2 → 3
...
最终结果：1 → 2 → 3 → 4 → 5 → 6

代码解析：

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 1. 创建虚拟头节点ListNode head = new ListNode(-1);ListNode ptr = head; // 新链表构建指针ListNode p1 = list1, p2 = list2;// 2. 双指针遍历比较while(p1 != null && p2 != null) {if(p1.val <= p2.val) {ptr.next = p1;   // 接入list1节点p1 = p1.next;    // list1指针后移} else {ptr.next = p2;   // 接入list2节点p2 = p2.next;    // list2指针后移}ptr = ptr.next;      // 新链表指针后移}// 3. 处理剩余节点ptr.next = p1 == null ? p2 : p1;// 4. 返回实际头节点return head.next;}
}

复杂度分析：

• 时间复杂度：O(m+n)
  需要完整遍历两个链表的所有节点（m和n分别为链表长度）
• 空间复杂度：O(1)
  仅使用固定数量的指针，无额外空间开销

关键优势：

1. 虚拟头节点避免空指针判断
2. 直接复用原链表节点（无new操作），节省空间
3. 剩余节点直接拼接，无需继续遍历
4. 清晰的线性逻辑，易于理解和维护

2. 两数相加

解题思路：两数相加（链表版）

核心思想：模拟竖式加法，逐位相加并处理进位。由于数字以逆序存储（低位在前），可以直接从链表头部开始相加。

关键步骤：

1. 初始化

   • 创建虚拟头节点 head 简化边界处理
   • 指针 current 指向当前结果链表的末尾
   • 进位标志 count 初始化为 0（表示无进位）

2. 双指针遍历链表

   • 同时遍历两个链表（允许链表长度不同）
   • 计算当前位总和：进位值 + l1当前值 + l2当前值
   • 注意处理链表长度不一致的情况（短链表用0补位）

3. 处理进位和当前位

   • 计算进位：count = 总和 / 10
   • 创建新节点存储当前位值：总和 % 10
   • 将新节点链接到结果链表

4. 处理最终进位

   • 遍历结束后检查剩余进位
   • 若进位不为0，需额外添加一个节点

5. 返回结果

   • 返回虚拟头节点的下一节点（实际头节点）

执行过程示例：

输入：
l1: 2 → 4 → 3  (表示342)
l2: 5 → 6 → 4  (表示465)计算过程：
1. 2+5=7     → 当前位7 进位0 → 节点7
2. 4+6=10   → 当前位0 进位1 → 节点0
3. 3+4+1=8  → 当前位8 进位0 → 节点8
4. 无剩余进位结果：7 → 0 → 8 (表示807)

代码解析：

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {// 1. 初始化虚拟头节点和进位ListNode head = new ListNode(-1);ListNode current = head;int count = 0; // 进位标志// 2. 双指针遍历链表ListNode p1 = l1, p2 = l2;while (p1 != null || p2 != null) {int sums = count; // 当前位总和初始化为进位值// 处理链表1的当前位（若存在）if (p1 != null) {sums += p1.val;p1 = p1.next;}// 处理链表2的当前位（若存在）if (p2 != null) {sums += p2.val;p2 = p2.next;}// 3. 计算进位和当前位值count = sums / 10;         // 更新进位int digit = sums % 10;     // 当前位值// 创建新节点并链接current.next = new ListNode(digit);current = current.next;}// 4. 处理最终进位if (count != 0) {current.next = new ListNode(count);}// 5. 返回实际头节点return head.next;}
}

算法特点：

• 时间复杂度：O(max(m,n))
  需遍历较长的链表（m和n分别为链表长度）
• 空间复杂度：O(max(m,n))
  结果链表长度最多为 max(m,n)+1（有进位时）
• 边界处理：
  • 虚拟头节点避免空链表判断
  • 自动处理不同长度链表
  • 最终进位单独处理

关键优势：

1. 完美处理进位传递（如 999+1=1000）
2. 自然处理不同长度链表（短链表自动补0）
3. 符合数学加法规则，清晰易懂
4. 严格遵循链表逆序存储的特性

19. 删除链表的倒数第N个结点

解题思路：删除链表的倒数第 N 个结点

核心思想：通过两次遍历链表实现删除操作。第一次遍历计算链表长度，第二次遍历定位到目标结点的前驱结点进行删除。

关键步骤：

1. 计算链表长度

   • 初始化指针 p 指向头结点
   • 遍历整个链表，统计结点数量 length
   • 时间复杂度：O(L)，其中 L 为链表长度

2. 确定目标位置

   • 计算要删除结点的正序位置：target = length - n + 1
   • 例如：链表长度 5，删除倒数第 2 个结点 → 正序第 4 个结点

3. 设置虚拟头结点

   • 创建虚拟头结点 dummy，其 next 指向实际头结点
   • 作用：统一处理删除头结点的特殊情况
   • 初始化当前指针 cur 指向虚拟头结点

4. 定位目标结点的前驱结点

   • 移动指针 cur 到目标位置的前一个结点
   • 移动次数：target - 1 次（因为从虚拟头结点开始计数）
   • 示例：删除第 4 个结点 → 需要移动到第 3 个结点

5. 执行删除操作

   • 修改指针：cur.next = cur.next.next
   • 跳过目标结点，完成删除

6. 返回结果

   • 返回虚拟头结点的 next（即新链表的头结点）

执行过程示例：

链表：1 → 2 → 3 → 4 → 5，删除倒数第 2 个结点（值为 4）步骤1：计算长度 length=5
步骤2：target = 5-2+1=4（删除第 4 个结点）
步骤3：虚拟头结点 dummy → 1 → 2 → 3 → 4 → 5
步骤4：cur 移动 3 次：dummy→1→2→3
步骤5：删除操作：3.next=3.next.next → 3→5
结果：1 → 2 → 3 → 5

代码解析：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 1. 计算链表长度ListNode p = head;int length = 0;while (p != null) {length++;p = p.next;}// 2. 计算目标位置int target = length - n + 1;// 3. 设置虚拟头结点ListNode dummy = new ListNode(0, head);ListNode cur = dummy;// 4. 定位到目标结点的前驱结点int count = 1;while (count < target) { // 循环 target-1 次cur = cur.next;count++;}// 5. 执行删除操作cur.next = cur.next.next;// 6. 返回新链表头结点return dummy.next;}
}

复杂度分析：

• 时间复杂度：O(L)
  两次遍历链表，总操作次数为 2L，渐进复杂度 O(L)
• 空间复杂度：O(1)
  仅使用固定数量的指针变量

边界情况处理：

1. 删除头结点（当 n = length 时）：

   链表：1→2→3，删除倒数第3个
   target = 3-3+1=1
   cur 停留在虚拟头结点
   删除操作：dummy.next = head.next
   返回：2→3
   

2. 删除尾结点（当 n = 1 时）：

   链表：1→2→3，删除倒数第1个
   target = 3-1+1=3
   cur 移动到第2个结点（值为2）
   删除操作：2.next = 2.next.next → 2→null
   结果：1→2
   

3. 单结点链表：

   链表：1，删除倒数第1个
   length=1, target=1
   cur 停留在虚拟头结点
   删除后返回 null
   

优化方向：可考虑使用双指针（快慢指针）实现一次遍历，快指针先走 n 步，然后快慢指针同步移动，当快指针到达尾部时，慢指针正好指向目标结点的前驱结点。

24. 两两交换链表中的节点

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {// 1.增加节点ListNode dummy = new ListNode(0,head);ListNode temp = dummy;while(temp.next!=null && temp.next.next!=null){ListNode node1 = temp.next;ListNode node2 = temp.next.next;temp.next = node2;node1.next = node2.next;node2.next = node1;temp = node1;}return dummy.next;}
}

解题思路：两两交换链表中的节点

这段代码实现了将链表中的节点两两交换的功能。以下是详细的解题思路描述：

问题理解

我们需要将链表中相邻的两个节点进行交换。例如：

• 输入：1 → 2 → 3 → 4
• 输出：2 → 1 → 4 → 3

解决思路

1. 虚拟头节点法：创建一个虚拟头节点(dummy node)来简化边界条件的处理
2. 迭代法：使用三个指针(temp, node1, node2)来遍历和交换节点
3. 逐步交换：每次处理两个相邻节点，然后移动到下一对节点

代码步骤详解

1. 创建虚拟头节点：

ListNode dummy = new ListNode(0,head);

创建一个值为0的虚拟头节点，其next指向真正的头节点。这样可以统一处理头节点交换的情况。

2. 初始化指针：

ListNode temp = dummy;

使用temp指针来跟踪当前处理的位置，初始指向虚拟头节点。

3. 循环交换节点：

while(temp.next!=null && temp.next.next!=null){
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;// 交换操作
temp.next = node2;// 步骤1：将前驱节点指向node2
node1.next = node2.next;// 步骤2：将node1指向node2的后继节点
node2.next = node1;// 步骤3：将node2指向node1temp = node1;// 步骤4：移动temp到下一对的前驱位置
}

交换过程图示：

初始状态：temp → node1 → node2 → ...
步骤1后：temp → node2 → node1 → node2.next
步骤2后：node1 → node2.next
步骤3后：node2 → node1
最终状态：temp → node2 → node1 → node2.next

4. 返回结果：

return dummy.next;

返回虚拟头节点的next，即交换后的新头节点。

关键点

• 虚拟头节点的使用简化了头节点交换的特殊情况处理
• 需要同时检查temp.next和temp.next.next不为null，确保有足够的节点可以交换
• 每次交换后，temp指针需要移动到交换后的node1位置（即下一对的前驱位置）
• 时间复杂度为O(n)，空间复杂度为O(1)（只使用了常数个额外指针）

这种方法通过清晰的指针操作实现了节点的两两交换，代码简洁且效率高。

138. 随机链表的复制

解题思路：复制带随机指针的链表

这段代码实现了复制一个带有随机指针的链表（Deep Copy）。以下是解题思路的详细描述：

问题理解

我们需要复制一个特殊的链表，其中每个节点除了有val值和指向下一个节点的next指针外，还有一个可能指向链表中任意节点或为null的random指针。

解决思路

1. 哈希表映射法：使用哈希表来建立原链表节点和复制链表节点之间的映射关系。
2. 两次遍历：

• 第一次遍历：创建所有新节点，并建立原节点到新节点的映射
• 第二次遍历：处理新节点的next和random指针

代码步骤详解

1. 边界检查：

if(head==null){
return null;
}

如果输入链表为空，直接返回null。

2. 第一次遍历 - 创建节点映射：

Node cur = head;
HashMap<Node,Node> map = new HashMap<>();
while(cur!=null){
map.put(cur,new Node(cur.val)); // 创建新节点并建立映射
cur = cur.next;
}

遍历原链表，为每个原节点创建一个新节点（只复制val值），并将这对节点存入哈希表。

3. 第二次遍历 - 设置指针关系：

cur = head;
while(cur!=null){
map.get(cur).next = map.get(cur.next); // 设置新节点的next指针
map.get(cur).random = map.get(cur.random); // 设置新节点的random指针
cur = cur.next;
}

再次遍历原链表，通过哈希表查找：

• 设置新节点的next指向对应的新节点
• 设置新节点的random指向对应的新节点

4. 返回结果：

return map.get(head);

返回新链表的头节点，即哈希表中与原链表头节点对应的新节点。

关键点

• 哈希表的使用是关键，它保存了原节点到新节点的映射，使得我们可以快速找到新节点之间的关系。
• 这种方法的时间复杂度是O(n)，空间复杂度是O(n)（因为使用了哈希表）。

这种方法优雅地解决了随机指针的复制问题，确保了新链表中的随机指针正确指向新链表中的对应节点，而不是原链表中的节点。

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {if(head==null){return null;}Node cur = head;HashMap<Node,Node> map = new HashMap<>();while(cur!=null){map.put(cur,new Node(cur.val));cur = cur.next;}cur = head;while(cur!=null){map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}return map.get(head);}
}

148. 排序链表

解题思路：链表排序（归并排序实现）

这段代码实现了对链表进行排序的功能，采用的是归并排序算法。以下是详细的解题思路描述：

解决思路

1. 归并排序：采用分治思想，将链表分成两半，分别排序后再合并
2. 快慢指针找中点：用于将链表平分为两部分
3. 递归排序：对分割后的子链表递归调用排序函数
4. 合并有序链表：将两个已排序的子链表合并为一个有序链表

代码步骤详解

主排序方法

public ListNode sortList(ListNode head) {
return sortList(head, null); // 初始调用，tail设为null
}

递归排序方法

public ListNode sortList(ListNode head, ListNode tail) {
// 基本情况1：空链表
if (head == null) {
return head;
}
// 基本情况2：只有一个节点（到达tail前一个节点）
if (head.next == tail) {
head.next = null; // 断开与后续节点的连接
return head;
}// 使用快慢指针找到链表中点
ListNode slow = head, fast = head;
while (fast != tail) {
slow = slow.next;
fast = fast.next;
if (fast != tail) {
fast = fast.next; // 快指针每次走两步
}
}
ListNode mid = slow; // 中点// 递归排序前后两部分
ListNode list1 = sortList(head, mid); // 排序前半部分
ListNode list2 = sortList(mid, tail); // 排序后半部分// 合并两个有序链表
return merge(list1, list2);
}

合并有序链表方法

public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0); // 虚拟头节点
ListNode temp = dummyHead; // 合并后的链表指针
ListNode temp1 = head1, temp2 = head2; // 两个子链表的指针// 比较两个链表的节点值，选择较小的加入结果链表
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}// 处理剩余节点
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}return dummyHead.next;
}

关键点分析

1. 分治策略：

• 将链表不断二分，直到子链表只有一个节点（自然有序）
• 然后逐步合并已排序的子链表

2. 快慢指针找中点：

• 快指针每次走两步，慢指针每次走一步
• 当快指针到达尾部时，慢指针正好在中点位置

3. 边界处理：

• 使用tail参数标记子链表的结束位置
• 当head.next == tail时，表示当前子链表只有一个节点

4. 合并过程：

• 使用虚拟头节点简化合并操作
• 比较两个子链表的当前节点值，选择较小的加入结果链表
• 处理剩余未合并的节点

复杂度分析

• 时间复杂度：O(n log n)，符合归并排序的时间复杂度
• 空间复杂度：O(log n)，递归调用栈的深度

这种方法充分利用了归并排序在链表结构上的优势，避免了数组归并排序中需要的额外空间，是链表排序的高效实现方式。