code/leetcode/v1/mergeklist

Posted on

Merge k Sorted Lists

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

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

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
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> nodes = new ArrayList<>();
        
        for (int i = 0; i < lists.length; i++) {
            while (lists[i] != null) {
                nodes.add(lists[i].val);
                lists[i] = lists[i].next;
            }
        }

        if (nodes.size() == 0)
            return null;
        
        nodes.sort(Comparator.naturalOrder());
        ListNode res = new ListNode(nodes.remove(0));
        ListNode p = res;
        
        for (int i = 0; i < nodes.size(); i++) {
            p.next = new ListNode(nodes.get(i));
            p = p.next;
        }
        
        return res;
    }
}

Reference
https://leetcode-cn.com/problems/merge-k-sorted-lists