合并k个排序链表

问题陈述

合并 k 个排序链表，返回合并后的排序链表。

示例：

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路分析

两个排序链表合并会吧？然后k个链表就两两合并啦。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
    public ListNode mergeKLinkedlist(ListNode[] lists){
        ListNode res=null;
        for(ListNode list:lists)
            res=mergeTwoLists(res,list);
        return res;
    }
    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        if(l1.val<l2.val){
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }
        l2.next=mergeTwoLists(l1,l2.next);
        return l2; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//两个有序链表归并的迭代法
class Solution{
    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        ListNode dummyNode=new ListNode(0);
        ListNode node=dummyNode;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                node.next=l1;
                l1=l1.next;
            }else{
                node.next=l2;
                l2=l2.next;
            }
            node=node.next;
        }
        node.next=l1==null? l2:l1;
        return dummyNode.next;
    }
}