首页 > 代码库 > Leetcode: Merge k Sorted List

Leetcode: Merge k Sorted List

2024-07-07 22:53:10   213人阅读

参看别人的思路，类似MergeSort的思路，思路是先分成两个子任务，然后递归求子任务，最后回溯回来。这个题目也是这样，先把k个list分成两半，然后继续划分，直到剩下两个list就合并起来，合并时会用到Merge Two Sorted Lists这道题。

 

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode mergeKLists(List<ListNode> lists) {
14         if (lists.size() == 0 || lists == null) {
15             return null;
16         }
17         return helper(lists, 0, lists.size()-1);
18     }
19     
20     public ListNode helper(List<ListNode> lists, int start, int end) {
21         if(start < end) {
22             int mid = (start + end) / 2;
23             return merge(helper(lists, start, mid), helper(lists, mid + 1, end));
24         }
25         return lists.get(start);
26     }
27     
28     public ListNode merge(ListNode l1, ListNode l2) {
29         // Start typing your Java solution below
30         // DO NOT write main() function
31         
32         ListNode dummyNode = new ListNode(0);
33         ListNode currentNode = dummyNode;
34         
35         while(l1!=null||l2!=null){
36             if(l1!=null&&l2!=null)
37                 if(l1.val>l2.val){
38                     currentNode.next =l2;
39                     l2 = l2.next;
40                 }else{
41                     currentNode.next =l1;
42                     l1 = l1.next;
43                 }
44             else if(l1==null){
45                 currentNode.next =l2;
46                     l2 = l2.next;
47             }else{
48                 currentNode.next =l1;
49                     l1 = l1.next;
50             }
51             currentNode=currentNode.next;
52                        
53         }
54         return dummyNode.next;
55         
56     }   
57 }

别人有一个更好的方法（未读）：

 1 public ListNode mergeKLists(ArrayList<ListNode> lists) {
 2     PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(10,new Comparator<ListNode>(){
 3             @Override
 4             public int compare(ListNode n1, ListNode n2)
 5             {
 6                 return n1.val-n2.val;
 7             }
 8         });
 9     for(int i=0;i<lists.size();i++)
10     {
11         ListNode node = lists.get(i); 
12      if(node!=null)
13      {
14       heap.offer(node);
15      }
16     }
17     ListNode head = null;
18     ListNode pre = head;
19     while(heap.size()>0)
20     {
21         ListNode cur = heap.poll();
22         if(head == null)
23         {
24             head = cur;
25             pre = head;
26         }
27         else
28         {
29             pre.next = cur;
30         }
31         pre = cur;
32         if(cur.next!=null)
33             heap.offer(cur.next);
34     }
35     return head;
36 }

 


联系
我们