当前位置：首页 > news >正文

LeetCode 热题 100 之 21. 合并两个有序链表 2. 两数相加 19. 删除链表的倒数第 N 个结点 24. 两两交换链表中的节点 25. K 个一组翻转链表

news 2026/8/21 17:57:46

21. 合并两个有序链表
2. 两数相加
19. 删除链表的倒数第 N 个结点
24. 两两交换链表中的节点
25. K 个一组翻转链表

21. 合并两个有序链表

/** * 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 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 ? l2 : l1; return dummy.next; } }

解题思路1：迭代法

创建一个虚拟头节点dummy，方便处理边界情况。

用指针curr指向当前合并的末尾节点，遍历两个有序链表l1和l2：

比较l1.val和l2.val，将较小的节点接在curr后面。
移动对应链表的指针和curr指针。

当其中一个链表遍历完毕后，将另一个链表的剩余部分直接接在curr后面。

class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val <= l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } }

解题思路2：递归法

递归终止条件：l1 == null或l2 == null，直接返回另一个非空链表。

递归逻辑：比较l1.val和l2.val，较小的节点的next指向剩余部分的合并结果，返回该较小节点。

2. 两数相加

这道题本质是模拟竖式加法，两个链表按逆序存储数字（个位在前），正好和加法从低位到高位的计算顺序一致，我们可以直接逐位相加并处理进位。

/** * 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 addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode curr = dummy; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int val1 = l1 != null ? l1.val : 0; int val2 = l2 != null ? l2.val : 0; int sum = val1 + val2 + carry; carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } return dummy.next; } }

解题思路1：迭代法

初始化：创建虚拟头节点dummy方便拼接结果，用carry记录进位，指针curr指向当前拼接位置。

遍历相加：同时遍历两个链表，只要任一链表未遍历完或还有进位，就继续计算：

取当前节点值（空节点则为 0），加上进位得到当前位总和。
新节点值 = 总和 % 10，新进位 = 总和 / 10。
将新节点拼接到curr后，移动curr指针。

返回结果：虚拟头节点的下一个节点即为最终结果链表。

class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return addTwo(l1, l2, 0); } // l1 和 l2 为当前遍历的节点，carry 为进位 private ListNode addTwo(ListNode l1, ListNode l2, int carry) { // 递归终止条件：两个链表都遍历完 + 无进位，无需生成新节点 if (l1 == null && l2 == null && carry == 0) { return null; } // 步骤1：计算当前位的总和（进位 + l1值 + l2值） int s = carry; if (l1 != null) { s += l1.val; l1 = l1.next; // 移动l1指针到下一位 } if (l2 != null) { s += l2.val; l2 = l2.next; // 移动l2指针到下一位 } // 步骤2：生成当前节点 + 递归处理下一位 // 当前节点值 = 总和 % 10（取余数） // 递归参数：下一位指针 + 新进位（总和 / 10，取商） return new ListNode(s % 10, addTwo(l1, l2, s / 10)); } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/add-two-numbers/solutions/2327008/dong-hua-jian-ji-xie-fa-cong-di-gui-dao-oe0di/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return addTwo(l1, l2, 0); } // l1 和 l2 为当前遍历的节点，carry 为进位 private ListNode addTwo(ListNode l1, ListNode l2, int carry) { if (l1 == null && l2 == null) { // 递归边界 return carry != 0 ? new ListNode(carry) : null; // 如果进位了，就额外创建一个节点 } if (l1 == null) { // 如果 l1 是空的，那么此时 l2 一定不是空节点 l1 = l2; l2 = null; // 交换 l1 与 l2，保证 l1 非空，从而简化代码 } int sum = carry + l1.val + (l2 != null ? l2.val : 0); // 节点值和进位加在一起 l1.val = sum % 10; // 每个节点保存一个数位（直接修改原链表） l1.next = addTwo(l1.next, (l2 != null ? l2.next : null), sum / 10); // 进位 return l1; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/add-two-numbers/solutions/2327008/dong-hua-jian-ji-xie-fa-cong-di-gui-dao-oe0di/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return addTwo(l1, l2, 0); } // l1 和 l2 为当前遍历的节点，carry 为进位 private ListNode addTwo(ListNode l1, ListNode l2, int carry) { if (l1 == null && l2 == null) { // 递归边界 return carry != 0 ? new ListNode(carry) : null; // 如果进位了，就额外创建一个节点 } if (l1 == null) { // 如果 l1 是空的，那么此时 l2 一定不是空节点 l1 = l2; l2 = null; // 交换 l1 与 l2，保证 l1 非空，从而简化代码 } int sum = carry + l1.val + (l2 != null ? l2.val : 0); // 节点值和进位加在一起 l1.val = sum % 10; // 每个节点保存一个数位（直接修改原链表） l1.next = addTwo(l1.next, (l2 != null ? l2.next : null), sum / 10); // 进位 return l1; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/add-two-numbers/solutions/2327008/dong-hua-jian-ji-xie-fa-cong-di-gui-dao-oe0di/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题思路2：递归法

看注释即可

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

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode slow = dummy; ListNode fast = dummy; // fast 先走 n 步 for (int i = 0; i < n; i++) { fast = fast.next; } // 同时移动，直到 fast 到末尾 while (fast.next != null) { slow = slow.next; fast = fast.next; } // 删除 slow 的下一个节点 slow.next = slow.next.next; return dummy.next; }

解题思路1：快慢指针法

创建虚拟头节点dummy，让slow和fast都指向它，方便处理删除头节点的边界情况。

让fast指针先向前走n步，此时slow和fast之间的距离正好是n。

然后slow和fast同时向前走，直到fast到达链表末尾。此时slow正好指向要删除节点的前一个节点。

修改slow.next = slow.next.next，完成删除操作，返回dummy.next。

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; int len = 0; ListNode curr = head; // 第一次遍历求长度 while (curr != null) { len++; curr = curr.next; } // 第二次遍历到要删除节点的前驱 curr = dummy; for (int i = 0; i < len - n; i++) { curr = curr.next; } curr.next = curr.next.next; return dummy.next; } }

解题思路2：两次遍历法

第一次遍历链表，计算总长度len。

第二次遍历到第len - 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) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; while (prev.next != null && prev.next.next != null) { ListNode first = prev.next; ListNode second = first.next; // 交换操作 prev.next = second; first.next = second.next; second.next = first; // 移动prev到下一组的前驱 prev = first; } return dummy.next; } }

解题思路1：迭代法

创建虚拟头节点dummy，让prev指向dummy，方便处理头节点交换的边界情况。

循环处理相邻节点对：

定义first = prev.next、second = first.next，若second为空则结束循环。
交换first和second的指向：
- prev.next = second（前驱指向第二个节点）
- first.next = second.next（第一个节点指向第三个节点）
- second.next = first（第二个节点指向第一个节点）
更新prev = first，继续处理下一组相邻节点。

返回dummy.next作为新链表头。

public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = head.next; head.next = swapPairs(newHead.next); newHead.next = head; return newHead; }

解题思路2：递归法

递归终止条件：head == null或head.next == null，直接返回head。

递归逻辑：

定义newHead = head.next（交换后的新头节点）。
head.next = swapPairs(newHead.next)（递归处理剩余节点，挂在原头节点后）。
newHead.next = head（新头节点指向原头节点，完成交换）。
返回newHead作为当前层的头节点。

25. K 个一组翻转链表

/** * 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 reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(0); dummy.next = head; // pre 指向当前组的前一个节点 ListNode pre = dummy; // end 指向当前组的最后一个节点 ListNode end = dummy; while (end.next != null) { // 找到第 k 个节点作为当前组的尾节点 for (int i = 0; i < k && end != null; i++) { end = end.next; } // 剩余节点不足 k 个，结束循环 if (end == null) break; // 记录下一组的起始节点 ListNode nextStart = end.next; // 记录当前组的起始节点 ListNode start = pre.next; // 断开当前组与下一组的连接，准备翻转 end.next = null; // 翻转当前组 pre.next = reverse(start); // 连接翻转后的组与下一组 start.next = nextStart; // 更新 pre 和 end 到下一组的位置 pre = start; end = start; } return dummy.next; } // 翻转单链表的辅助函数 private ListNode reverse(ListNode head) { ListNode pre = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = pre; pre = curr; curr = next; } return pre; } }

解题思路1：迭代法（模拟分组翻转）

用dummy节点作为新链表的头部，方便处理原头节点变化的情况。

每次找到当前组的尾节点，若剩余节点不足k个则停止。

翻转当前组内的k个节点，再将翻转后的组与前后组连接。

public class Solution { public ListNode reverseKGroup(ListNode head, int k) { // 递归终止条件：当前头节点为空，或剩余节点不足 k 个 if (head == null) return null; ListNode end = head; for (int i = 0; i < k; i++) { if (end == null) return head; end = end.next; } // 翻转当前组的 k 个节点 ListNode newHead = reverse(head, end); // 原头节点变为当前组的尾节点，连接到下一组的翻转结果 head.next = reverseKGroup(end, k); return newHead; } // 翻转 [head, end) 区间的链表，返回新的头节点 private ListNode reverse(ListNode head, ListNode end) { ListNode pre = null; ListNode curr = head; while (curr != end) { ListNode next = curr.next; curr.next = pre; pre = curr; curr = next; } return pre; } }

解题思路2：递归法

利用递归的分治思想，先处理后面的组，再翻转当前组。

先找到第k个节点，作为当前组的尾节点。
递归翻转第k+1个节点开始的子链表。
翻转当前组的k个节点，并将当前组的原头节点连接到递归返回的子链表头节点。

import java.util.Deque; import java.util.LinkedList; public class Solution { public ListNode reverseKGroup(ListNode head, int k) { Deque<ListNode> stack = new LinkedList<>(); ListNode dummy = new ListNode(0); // p 用于构建新链表 ListNode p = dummy; while (true) { int count = 0; ListNode tmp = head; // 尝试将 k 个节点入栈 while (tmp != null && count < k) { stack.push(tmp); tmp = tmp.next; count++; } // 剩余节点不足 k 个，结束循环 if (count < k) { p.next = head; break; } // 弹出栈中节点，完成组内翻转 while (!stack.isEmpty()) { p.next = stack.pop(); p = p.next; } // 移动到下一组 head = tmp; } return dummy.next; } }