23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution

(1) Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> q = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            public int compare(ListNode n1, ListNode n2) {
                return n1.val-n2.val;
            } 
        });
        ListNode head = null;
        ListNode prev = null;
        for (ListNode node : lists) {
            if (node != null) {
                q.offer(node);
            }
        }
        while (q.size() > 0) {
            if (head == null) {
                head = q.poll();
                prev = head;
                if (head.next != null) {
                    q.offer(head.next);
                } 
            } else {
                ListNode node = q.poll();
                prev.next = node;
                prev = node;
                if (node.next != null) {
                    q.offer(node.next);
                }
            }
        }
        return head;
    }
}

(2) Python

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists:
            return None
        q = []
        for node in lists:
            if node:
                q.append((node.val, node))
        heapq.heapify(q)
        head = None
        prev = None
        while q:
            if not head:
                val, nt = heapq.heappop(q)
                head = nt
                prev = head
                if head.next:
                    heapq.heappush(q, (head.next.val, head.next))
            else:
                val,nt = heapq.heappop(q)
                prev.next = nt
                prev = nt
                if nt.next:
                    heapq.heappush(q, (nt.next.val, nt.next))
        return head

(3) Scala

/**
 * Definition for singly-linked list.
 * class ListNode(var _x: Int = 0) {
 *   var next: ListNode = null
 *   var x: Int = _x
 * }
 */
object Solution {
    def mergeKLists(lists: Array[ListNode]): ListNode = {
        def comp(node: ListNode) = -node.x

        import scala.collection.mutable.PriorityQueue
        var q: PriorityQueue[ListNode] = PriorityQueue()(Ordering.by(comp))
        for (node<-lists) {
            if (node != null) {
                q.enqueue(node)
            }
        }
        var head: ListNode = null
        var prev: ListNode = head
        while (q.size > 0) {
            val node: ListNode = q.dequeue()
            if (head == null) {
                head = node
                prev = node
                if (node.next != null) {
                    q.enqueue(node.next)
                }
            } else {
                prev.next = node
                prev = node
                if (node.next != null) {
                    q.enqueue(node.next)
                }
            }
        }
        return head
    }
}

results matching ""

    No results matching ""