坚持刷题｜合并有序链表

题目

21. 合并两个有序链表

思考

合并有序链表这一算法问题主要考察以下几个关键点

1. 链表操作：理解链表数据结构以及如何遍历、比较、连接链表节点。
2. 边界条件处理：包括处理一个或两个链表为空的情况，以及其中一个链表先到达末尾的场景。
3. 递归与迭代：可以选择递归或迭代的方法来解决问题，每种方法都有其优缺点，需要理解何时使用哪一种。
4. 效率考量：优化算法的时间复杂度和空间复杂度，例如使用优先队列可以达到较好的时间性能。
5. 代码整洁性：写出清晰、可读性强的代码，避免不必要的复杂性和冗余。
6. 错误处理：在实际编码中，考虑到可能出现的异常情况，比如处理null指针异常。
7. 算法设计：理解不同算法策略，如两两合并法、使用辅助数据结构等。
8. 优化技巧：了解如何在不增加额外空间复杂度的情况下解决问题，例如原地修改链表而非创建新的链表。
9. 测试用例：编写全面的测试用例验证代码的正确性，包括极端情况和常见情况。
10. 性能分析：能够分析和解释算法的时间和空间复杂度，理解为什么某种方法优于其他方法。

代码实现

合并两个有序链表是一个常见的链表操作，可以通过迭代或递归的方式实现。

迭代

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;if(amount==0){return null;}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类来实现，因为这个类内部就是使用数组实现的最小堆。

基本操作

1. 插入元素 (offer 或 add)：将一个元素添加到堆中，同时保持堆的性质不变，但是当队列已满时，add会抛出异常，而offer则返回false。
2. 删除最小元素 (poll)：从堆中移除并返回最小的元素。
3. 获取最小元素 (peek)：返回但不移除最小的元素。
4. 移除并返回队列头部的元素（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，它将字符串按照长度进行排序。