【每日一题】【小根堆&边出队边入队后续节点&注意判空】23. 合并K个升序链表-211128/220213

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

答案1（参数是数组）：

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        if(lists.length == 0) {

            return null;

        }

        ListNode dummy = new ListNode(0);

        ListNode cur = dummy;

        //后大前小

        PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);

        for(ListNode list : lists) {

            if(list == null) {

                continue;

            }

            pq.add(list);

        }

        while(!pq.isEmpty()) {

            ListNode next = pq.poll();

            cur.next = next;

            cur = cur.next;

            if(next.next != null) {

                pq.add(next.next);

            }

        }

        return dummy.next;

    }

}

答案2：（参数是ArrayList）

import java.util.*;

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode mergeKLists(ArrayList<ListNode> lists) {

        ListNode res = new ListNode(0);

        ListNode cur = res;

        PriorityQueue<ListNode> queue =

            new PriorityQueue<>((o1, o2) -> o1.val - o2.val);

        for(ListNode list : lists) {

            if(list != null) {

                queue.add(list);

            }

        }

        while(!queue.isEmpty()) {

            ListNode node = queue.poll();

            if(node == null) {

                continue;

            }

            cur.next = node;

            cur = cur.next;

            if(node.next != null) {

                queue.offer(node.next);

            }

        }

        return res.next;

    }

}

自己方法：（超时）

import java.util.*;

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

public class Solution {

    public ListNode mergeKLists(ArrayList<ListNode> lists) {

        //使用优先队列（小根堆）

        PriorityQueue<ListNode> queue =

            new PriorityQueue<>((o1, o2) -> o1.val - o2.val);

        ListNode res = new ListNode(0);

        ListNode cur = res;

        Iterator<ListNode> iter = lists.iterator();

        while(iter.hasNext()) {

            ListNode list = iter.next();

            while(list != null) {

                queue.add(list);

                list = list.next;

            }

        }

        while(!queue.isEmpty()) {

            cur.next = queue.poll();

            cur = cur.next;

        }

        return res.next;

    }

}

【每日一题】【小根堆&边出队边入队后续节点&注意判空】23. 合并K个升序链表-211128/220213的相关教程结束。