目录
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
什么是链表？
链表（Linked List）是一种常见的数据结构，它由一组节点（Node）组成，每个节点包含数据部分和指向下一个节点的引用。与数组不同，链表中的元素不需要连续存储，因此插入和删除操作非常高效，但随机访问元素的效率较低。
在 Java 中，链表可以通过自定义的类来实现，每个节点通常定义为一个内部类。Java 也有内置的链表实现，比如 LinkedList 类，它是 Java 集合框架的一部分。
链表的基本概念：
-
节点（Node）： 每个节点包含两个部分：
- 数据部分：存储具体的数值或对象。
- 指针部分：存储指向下一个节点的引用（对于单向链表）或上下两个节点的引用（对于双向链表）。
-
链表类型：
- 单向链表（Singly Linked List）：每个节点只指向下一个节点。
- 双向链表（Doubly Linked List）：每个节点同时指向前后两个节点。
- 循环链表（Circular Linked List）：链表的最后一个节点指向第一个节点，形成一个循环。
-
基本操作：
- 插入（Insertion）：可以在链表头、链表尾或任意位置插入新节点。
- 删除（Deletion）：可以删除链表头、链表尾或指定位置的节点。
- 查找（Search）：遍历链表寻找特定的元素。
- 遍历（Traversal）：从头到尾依次访问每个节点。
Java 中的链表实现
- 自定义单向链表：
你可以自己实现一个简单的链表类，如下：
class ListNode {
int val; // 节点的值
ListNode next; // 指向下一个节点的引用
// 构造方法
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class LinkedList {
private ListNode head; // 链表的头节点
// 在链表末尾插入新节点
public void insert(int value) {
ListNode newNode = new ListNode(value);
if (head == null) {
head = newNode;
} else {
ListNode current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// 遍历链表并打印所有节点的值
public void printList() {
ListNode current = head;
while (current != null) {
System.out.print(current.val + " ");
current = current.next;
}
System.out.println();
}
}
使用自定义链表：
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.printList(); // 输出: 1 2 3
}
}
-
Java 内置
LinkedList类：
Java 提供了内置的 LinkedList 类，它是一个双向链表，实现了 List 和 Deque 接口。可以用它方便地进行各种链表操作。
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
// 添加元素
list.add(1);
list.add(2);
list.add(3);
// 遍历链表
for (int value : list) {
System.out.print(value + " ");
}
System.out.println();
// 移除第一个元素
list.removeFirst();
System.out.println("After removing first element: " + list);
}
}
回到题目
解题思路
-
创建虚拟头节点：
- 由于合并的链表可能从任意一个链表开始，我们可以使用一个虚拟头节点（
prehead），避免处理特殊情况（如合并后的链表为空或只包含一个节点）。 - 虚拟头节点本身不会包含有效的数据，最终返回结果时直接返回虚拟头节点的下一个节点即可。
- 由于合并的链表可能从任意一个链表开始，我们可以使用一个虚拟头节点（
-
遍历两个链表：
- 用两个指针
l1和l2分别指向两个链表的头节点。 - 在每次遍历时，比较两个链表当前节点的值，将值较小的节点加入结果链表，然后移动对应的指针到下一个节点。
- 这样每次都保证结果链表中的节点是有序的。
- 用两个指针
-
处理剩余节点：
- 在合并过程中，两个链表的长度可能不同。当其中一个链表遍历完后，另一个链表可能还有剩余节点。
- 由于剩下的节点已经是有序的，因此只需将剩余的链表直接连接到结果链表的尾部。
-
返回结果链表：
- 最终返回虚拟头节点
prehead的下一个节点，即完整的合并后的链表。
- 最终返回虚拟头节点
代码实现
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 创建一个虚拟头节点，用于简化处理逻辑
ListNode prehead = new ListNode(-1);
// 用一个指针 prev 指向当前合并链表的最后一个节点
ListNode prev = prehead;
// 当两个链表都不为空时，遍历它们
while (l1 != null && l2 != null) {
// 如果 l1 当前节点值小于等于 l2 当前节点值
if (l1.val <= l2.val) {
// 将 l1 当前节点接到 prev 的后面
prev.next = l1;
// l1 移动到下一个节点
l1 = l1.next;
} else {
// 如果 l2 当前节点值较小，将 l2 当前节点接到 prev 的后面
prev.next = l2;
// l2 移动到下一个节点
l2 = l2.next;
}
// prev 指针也前进到新的最后一个节点
prev = prev.next;
}
// 合并后，l1 和 l2 最多只剩下一个未合并完，直接连接剩余部分
prev.next = (l1 == null) ? l2 : l1;
// 返回合并后的链表，跳过虚拟头节点
return prehead.next;
}
}
总结：
这段代码通过双指针和虚拟头节点的方式，优雅地解决了两个有序链表合并的问题。它的时间复杂度是 O(n + m)，其中 n 和 m 分别是两个链表的长度，因为我们需要遍历两个链表的每个节点。