1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode mergeKLists(ListNode[] lists) {
13

14
        if(lists.length ==  0) {
15
            return null;
16
        }
17
        // if(lists.length == 1) {
18
        //     return lists[0];
19
        // }
20
        for(int i = 1; i < lists.length; i++) {
21
            lists[i] = merge2Lists(lists[i-1], lists[i]);
22
        }
23
        return lists[lists.length - 1];
24
    }
25
    public ListNode merge2Lists(ListNode l1, ListNode l2) {
26
        ListNode newList = new ListNode();
27
        ListNode curr = newList;
28
        while(l1 != null && l2 != null) {
29
            if(l1.val < l2.val) {
30
                curr.next = l1;
31
                l1 = l1.next;
32
            } else {
33
                curr.next = l2;
34
                l2 = l2.next;
35
            }
36
            curr = curr.next;
37
        }
38
        if(l1 == null) {
39
            curr.next = l2;
40
        }
41
        if(l2 == null) {
42
            curr.next = l1;
43
        }
44
        return newList.next;
45
    }
46
}