力扣第 21 题「 合并两个有序链表」

  1. //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
  2. //
  3. // 
  4. //
  5. // 示例 1： 
  6. //
  7. // 
  8. //输入：l1 = [1,2,4], l2 = [1,3,4]
  9. //输出：[1,1,2,3,4,4]
  10. // 
  11. //
  12. // 示例 2： 
  13. //
  14. // 
  15. //输入：l1 = [], l2 = []
  16. //输出：[]
  17. // 
  18. //
  19. // 示例 3： 
  20. //
  21. // 
  22. //输入：l1 = [], l2 = [0]
  23. //输出：[0]
  24. // 
  25. //
  26. // 
  27. //
  28. // 提示： 
  29. //
  30. // 
  31. // 两个链表的节点数目范围是 [0, 50] 
  32. // -100 <= Node.val <= 100 
  33. // l1 和 l2 均按 非递减顺序 排列 
  34. // 
  35. // Related Topics 递归 链表 
  36. // 👍 2346 👎 0
  39. //leetcode submit region begin(Prohibit modification and deletion)
  40. /**
  41.  * Definition for singly-linked list.
  42.  * public class ListNode {
  43.  *     int val;
  44.  *     ListNode next;
  45.  *     ListNode() {}
  46.  *     ListNode(int val) { this.val = val; }
  47.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  48.  * }
  49.  */
  50. class Solution {
  51.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  52.         // 记录最终结果头结点
  53.         ListNode res = new ListNode(-1);
  54.         // 增加res引用，用于链表前进
  55.         ListNode temp = res;
  56.         // 判断两个链表null
  57.         while (list1 != null && list2 != null) {
  58.             // 值小的加入到结果链表上，链表前进一步
  59.             if (list1.val < list2.val) {
  60.                 temp.next = list1;
  61.                 list1 = list1.next;
  62.             } else {
  63.                 temp.next = list2;
  64.                 list2 = list2.next;
  65.             }
  66.             temp = temp.next;
  67.         }
  68.         if (list1 != null) {
  69.             temp.next = list1;
  70.             // list2为null，将list1后面所有链表加入就行，不需要链表前进了
  71.             // list1 = list1.next;
  72.         }
  73.         if (list2 != null) {
  74.             temp.next = list2;
  75.             // list2 = list2.next;
  76.         }
  77.         return res.next;
  78.     }
  79. }
  80. //leetcode submit region end(Prohibit modification and deletion)

力扣第 23 题「 合并K个升序链表」：

合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？
这里我们就要用到 优先级队列（二叉堆） 这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点：

  1. ListNode mergeKLists(ListNode[] lists) {
  2.     if (lists.length == 0) return null;
  3.     // 虚拟头结点
  4.     ListNode dummy = new ListNode(-1);
  5.     ListNode p = dummy;
  6.     // 优先级队列，最小堆
  7.     PriorityQueue<ListNode> pq = new PriorityQueue<>(
  8.         lists.length, (a, b)->(a.val - b.val));
  9.     // 将 k 个链表的头结点加入最小堆
  10.     for (ListNode head : lists) {
  11.         if (head != null)
  12.             pq.add(head);
  13.     }
  15.     while (!pq.isEmpty()) {
  16.         // 获取最小节点，接到结果链表中
  17.         ListNode node = pq.poll();
  18.         p.next = node;
  19.         if (node.next != null) {
  20.             pq.add(node.next);
  21.         }
  22.         // p 指针不断前进
  23.         p = p.next;
  24.     }
  25.     return dummy.next;
  26. }

参考：

https://labuladong.github.io/algo/1/9/