【链表】合并k个已排序的链表

BM5 合并k个已排序的链表
https://www.nowcoder.com/practice
描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

mport java.util.*;
public class Solution {

    public ListNode merge(ListNode list1, ListNode list2){
        if(list1 == null || list2 == null) return list1 == null? list2 : list1;
        ListNode dummy = new ListNode(-1), t = dummy;
        ListNode p = list1;
        ListNode q = list2;
        while(p != null && q != null){
            if(p.val < q.val){
                t.next = p;
                p = p.next;
                
            }else{
                t.next = q;
                q = q.next;
            }
            t = t.next;
        }
        if(p != null) t.next = p;
        if(q != null) t.next = q;
        return dummy.next;
    }

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.size() == 0) return null;
        if(lists.size() == 1) return lists.get(0);
        ListNode t = lists.get(0);
        for(int i = 1; i < lists.size(); i++){
            t = merge(t, lists.get(i));
        }
        return t;
    }
}
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