合并两个有序链表

问题1

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

原理

• 创建一个新的链表，定义好头结点
• 循环两个升序链表，找到较小的值插入到新的链表
• 把剩余的链表补充到新的链表尾部

代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode newHead = new ListNode(-1);
        ListNode run = newHead;

        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                run.next =l1;
                l1 = l1.next;
            }else{
                run.next = l2;
                l2 = l2.next;
            }
            run = run.next;
        }
        if(l1!=null){
            run.next = l1;
        }
        if(l2!=null){
            run.next = l2;
        }
        return newHead.next;
    }
}

注意事项

• 第一，不要忘了移动l1 和l2
• 第二，不要忘了把剩余的l1或者l2追加到新的链表尾部

问题2

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

原理

• 多个有序链表合并，可以联想到优先队列
• 将数组中的每一个链表首节点放入到优先队列
• 遍历优先队列的元素放入新的链表里，然后把出队元素的后继节点加入优先队列

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length<=0){
            return null;
        }

        PriorityQueue<ListNode> pq = new PriorityQueue<>((o1,o2)->o1.val-o2.val);
        for(ListNode l:lists){
            if(l!=null){
                pq.add(l);
            }
        }

        ListNode newHead = new ListNode(-1);
        ListNode run = newHead;

        while(!pq.isEmpty()){
            ListNode cur = pq.poll();
            run.next = cur;
            run = run.next;
            if(cur.next!=null){
                pq.add(cur.next);
            }
        }
        return newHead.next;
    }
}

注意事项

• 注意在往优先队列放入元素的时候考虑为空的情况