23. 合并 K 個升序鏈表 - 力扣（LeetCode）

1.數組排序

思路

（1）將全部的節點存儲到數組中

（2）對數組進行排序

（3）最后創建一個全新的鏈表

具體代碼

/*** 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) {int len=0;for(int i=0;i<lists.length;i++){ListNode p = lists[i];while(p!=null){len++;p=p.next;}}int[] arr = new int[len];int k=0;for(int i=0;i<lists.length;i++){ListNode p = lists[i];while(p!=null){arr[k++]=p.val;p=p.next;}}Arrays.sort(arr);ListNode head = new ListNode();ListNode ans = head;for(int i=0;i<len;i++){ListNode newn = new ListNode();newn.val=arr[i];head.next=newn;head=newn;}return ans.next;}
}

2.兩兩比較合成鏈表

思路

兩兩合并，也就是for循環，每次兩個鏈表進行合并，最后輸出結果。

具體步驟：

（1）判斷鏈表是否為空，不是空則p=lists[0]

（2）將p與lists中下一個列表合并，采用之前寫過的兩兩合并方法。

（3）每次結束后后需要將p歸為到原始節點，重新與下一個鏈表合并。

具體代碼

/*** 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) {if(lists.length==0){return null;}ListNode p = lists[0];  for(int i=1 ; i<lists.length;i++){ListNode con = new ListNode();ListNode init = con;ListNode np = lists[i];while(p != null && np != null){if(p.val<=np.val){con.next=p;con=con.next;p=p.next;}else{con.next=np;con=con.next;np=np.next;}}if(p==null){con.next=np;}else{con.next=p;}p=init.next;}return p;}
}

3.優先隊列

思路

將鏈表放入優先隊列中（小頂堆），每次循環都去最小的加入新鏈表，直到隊列為空。

具體步驟：
（1）構造優先隊列

（2）將各個鏈表的首節點放入隊列

（3）將最小的節點加入鏈表，然后該節點進入下一個位置，如果不是空的，則加入隊列。

具體代碼

/*** 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) {PriorityQueue<ListNode> pq = new PriorityQueue<>((o1,o2)->{return o1.val-o2.val;});for(ListNode node:lists){if(node!=null){pq.offer(node);}}ListNode ans = new ListNode();ListNode cur = ans;while(!pq.isEmpty()){ListNode s=pq.poll();cur.next=s;cur=cur.next;if(s.next!=null){s=s.next;pq.offer(s);}}return ans.next;}
}