34.合并 K 个升序链表

LCR 078. 合并 K 个升序链表

给定一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

方法1： 保存val值到ArrayList，并排序。再新建结点存入val

/*** 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 mergeKLists(ListNode[] lists) {// HashMap<Integer, ListNode> map = new HashMap<Integer, ListNode>();ArrayList<Integer> values = new ArrayList<>();for(ListNode head : lists){ListNode tmp = head;while(tmp != null){values.add(tmp.val);tmp = tmp.next;}}Collections.sort(values);// 重建排序后的链表ListNode dummy = new ListNode(); // 哑节点，简化链表操作ListNode tmp = dummy;for (int val : values) {tmp.next = new ListNode(val); // 新建节点，避免原节点指针干扰tmp = tmp.next;}return dummy.next;}
}

 

方法2：  顺序合并——链表合并思路，逐个将待加入链表合并入 ans  指向的新链表中。

用一个变量 ans 来维护以及合并的链表，第 i 次循环把第 i 个链表和 ans 合并，答案保存到 ans 中。

/*** 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 mergeKLists(ListNode[] lists) {// ListNode ans = new ListNode();      错误写法——>因为 new ListNode();默认初始化值为0ListNode ans = null;for(ListNode head:lists){ans = merge(head, ans);}return ans;}public ListNode merge(ListNode a, ListNode b){if(a == null || b == null) return a = a==null? b:a;ListNode dummy = new ListNode(0);ListNode tmp = dummy;while(a!=null && b!=null){if(a.val <= b.val){tmp.next=a;a=a.next;tmp=tmp.next;}else{tmp.next=b;b=b.next;tmp=tmp.next;}}tmp.next = a==null?b:a;return dummy.next;}
}