My Submissions

Total Accepted: 121007 Total Submissions: 469882 Difficulty: Hard Contributors: Admin

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Hide Company Tags  LinkedIn Google Uber Airbnb Facebook Twitter Amazon Microsoft Hide Tags  Divide and Conquer Linked List Heap Hide Similar Problems  (E) Merge Two Sorted Lists (M) Ugly Number II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
      return partition(lists, 0, lists.length - 1);
    }
    
    public ListNode partition(ListNode[] lists, int s, int e) {
        if (s == e) return lists[s];
        
        if (s < e) {
            int m = (s + e) / 2;
            ListNode l1 = partition(lists, s, m);
            ListNode l2 = partition(lists, m + 1, e);
            return merge(l1, l2);
        } else {
            return null;
        }
    }
    
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode p = res;
        
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                p.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            p = p.next;
        }
        
        if (l1 != null) p.next = l1;
        if (l2 != null) p.next = l2;
        return res.next;
    }
}