1、合并两个有序链表leetcode21

 

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 虚拟头结点
        ListNode dummy = new ListNode(-1), p = dummy;
        ListNode p1 = l1, p2 = l2;

        while (p1 != null && p2 != null) {
            // 比较 p1 和 p2 两个指针
            // 将值较小的的节点接到 p 指针
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            // p 指针不断前进
            p = p.next;
        }

        if (p1 != null) {
            p.next = p1;
        }

        if (p2 != null) {
            p.next = p2;
        }

        return dummy.next;
    }
}

---

2、合并k个升序链表leetcode23

 

class Solution{
public ListNode mergeKLists(ListNode[] lists){
if(lists.length==0)
return null;
//虚拟头节点
ListNode dummy=new ListNode(-1);
ListNode p=dummy;
PriorityQueue<ListNode>pq=new PriorityQueue<>(
lists.length,(a,b)->(a.val-b.val)
);


for(ListNode head:lists){
 if(head!=null)
pq.add(head);
}

while(!pq.isEmpty()){

ListNode node=pq.poll();
p.next=node;
if(node.next!=null){
pq.add(node.next);
}
p=p.next;
}
return dummy.next;
}
}