文章目录
- 题目
- 思考
- 代码实现
- 迭代
- 递归
- 扩展
- 实现k个有序链表合并
- 方法一
- 方法二
- PriorityQueue
- 基本操作
- Java示例
- 注意事项
Hello，大家好，我是阿月。坚持刷题，老年痴呆追不上我，消失了一段时间，我又回来刷题啦，今天先刷个简单的：合并有序链表
题目
21. 合并两个有序链表
思考
合并有序链表这一算法问题主要考察以下几个关键点
- 链表操作：理解链表数据结构以及如何遍历、比较、连接链表节点。
- 边界条件处理：包括处理一个或两个链表为空的情况，以及其中一个链表先到达末尾的场景。
- 递归与迭代：可以选择递归或迭代的方法来解决问题，每种方法都有其优缺点，需要理解何时使用哪一种。
- 效率考量：优化算法的时间复杂度和空间复杂度，例如使用优先队列可以达到较好的时间性能。
- 代码整洁性：写出清晰、可读性强的代码，避免不必要的复杂性和冗余。
- 错误处理：在实际编码中，考虑到可能出现的异常情况，比如处理
null指针异常。 - 算法设计：理解不同算法策略，如两两合并法、使用辅助数据结构等。
- 优化技巧：了解如何在不增加额外空间复杂度的情况下解决问题，例如原地修改链表而非创建新的链表。
- 测试用例：编写全面的测试用例验证代码的正确性，包括极端情况和常见情况。
- 性能分析：能够分析和解释算法的时间和空间复杂度，理解为什么某种方法优于其他方法。
代码实现
合并两个有序链表是一个常见的链表操作，可以通过迭代或递归的方式实现。
迭代
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 == null ? l2 : l1;
return dummy.next;
}
}
在这段代码中，我们首先创建一个虚拟头节点dummy和一个指针cur指向dummy。然后我们遍历两个链表，每次都把较小的节点接到cur的后面，并移动cur和较小节点所在链表的头指针。当一个链表遍历完后，我们就直接把另一个链表接到cur的后面。最后返回dummy.next就是合并后的链表。
递归
使用递归的方式来合并两个有序链表是一种直观且简洁的方法。以下是使用Java实现的示例代码：
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public 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;
}
}
}
在上述代码中，mergeTwoLists方法接受两个链表的头节点l1和l2作为参数。该方法首先检查两个链表是否为空。如果其中一个链表为空，那么就直接返回另一个链表，因为这意味着另一个链表已经是合并后的结果。
如果两个链表都不为空，那么就比较两个链表头节点的值。如果l1的值小于l2的值，那么就将l1的next字段设置为l1.next和l2合并的结果，然后返回l1。反之亦然，如果l2的值小于等于l1的值，那么就将l2的next字段设置为l1和l2.next合并的结果，然后返回l2。
这种方法利用了递归的特性，逐步将大问题分解成小问题，直到问题简单到可以直接解决（即一个链表为空）。由于递归的深度最多为链表的长度，因此这种方法的时间复杂度为O(n)，其中n为两个链表中节点的总数。
扩展
实现k个有序链表合并
方法一
我们可以使用分治的策略，将K个链表两两合并，直到剩下最后一个链表。这就是所谓的"两两合并"策略。以下是使用Java实现的代码：
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int amount = lists.length;
int interval = 1;
while (interval < amount) {
for (int i = 0; i < amount - interval; i += interval * 2) {
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
}
interval *= 2;
}
return lists[0];
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 == null ? l2 : l1;
return dummy.next;
}
}
在这个代码中，我们首先定义了一个mergeTwoLists方法用于合并两个有序链表。然后在mergeKLists方法中，我们使用了"两两合并"的策略来合并K个有序链表。
这种方法的时间复杂度为O(N log K)，其中N是所有链表中节点的总数，K是链表的数量。空间复杂度为O(1)。
方法二
在Java中，我们还可以使用 PriorityQueue 来实现。
import java.util.PriorityQueue;
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
for (ListNode node : lists) {
if (node != null) {
queue.add(node);
}
}
while (!queue.isEmpty()) {
ListNode node = queue.poll();
tail.next = node;
tail = tail.next;
if (node.next != null) {
queue.add(node.next);
}
}
return dummy.next;
}
}
在这个解决方案中，我们首先创建一个虚拟头节点和一个尾节点，然后遍历所有的链表，将每个链表的头节点放入优先队列中。然后我们开始循环处理优先队列，每次从队列中取出最小的元素，将其添加到结果链表中，然后将其下一个节点（如果存在）放入队列中。最后返回虚拟头节点的下一个节点，即为合并后的链表的头节点。
- 注意，Java中的 PriorityQueue 默认是按照自然顺序排序的，所以我们需要提供一个比较器来确保按照节点的值进行排序。
PriorityQueue是Java集合框架的一部分，它是一个基于优先堆的无界优先队列。此队列按照元素的自然排序进行排序，或者根据构造队列时提供的Comparator进行排序，具体取决于使用的构造方法。
PriorityQueue
最小堆是一种特殊的完全二叉树结构，其中每个父节点的值都小于或等于其子节点的值。这种结构保证了堆的根节点始终是最小的元素，从而使得查找最小元素的操作非常快速。最小堆在Java中可以通过java.util.PriorityQueue类来实现，因为这个类内部就是使用数组实现的最小堆。
基本操作
- 插入元素 (
offer或add)：将一个元素添加到堆中，同时保持堆的性质不变，但是当队列已满时，add会抛出异常，而offer则返回false。 - 删除最小元素 (
poll)：从堆中移除并返回最小的元素。 - 获取最小元素 (
peek)：返回但不移除最小的元素。 - 移除并返回队列头部的元素（remove）：如果队列为空，则抛出NoSuchElementException异常。
Java示例
首先，我们创建一个PriorityQueue实例，这将作为我们的最小堆：
import java.util.PriorityQueue;
public class MinHeapExample {
public static void main(String[] args) {
// 创建一个最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 插入元素
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.offer(4);
System.out.println("堆中的元素：" + minHeap);
// 获取最小元素
Integer smallest = minHeap.peek();
System.out.println("最小元素是：" + smallest);
// 删除最小元素
Integer removed = minHeap.poll();
System.out.println("删除的最小元素：" + removed);
System.out.println("删除后堆中的元素：" + minHeap);
}
}
运行上述代码，你将看到如下输出：
堆中的元素：[1, 4, 3, 5]
最小元素是：1
删除的最小元素：1
删除后堆中的元素：[3, 4, 5]
注意事项
PriorityQueue默认情况下实现的是最小堆，如果要实现最大堆，可以自定义比较器Comparator。PriorityQueue不允许插入null元素，否则会抛出NullPointerException。PriorityQueue没有固定大小，它可以动态调整大小。- 通过上面的示例，可以看到
PriorityQueue如何在内部自动维护堆的性质，使得最小元素始终位于堆的顶部，方便我们进行高效的查找和删除操作。 PriorityQueue的一个重要特性是它的元素必须是可比较的，也就是说，它们必须实现了Comparable接口，或者在创建PriorityQueue时提供了一个Comparator。
例如，下面的代码创建了一个按照字符串长度排序的PriorityQueue：
PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
});
在这个例子中，我们提供了一个Comparator，它将字符串按照长度进行排序。
