Using queue and mergeTwoArray


  • 0
    E

    Here i use queue and #21 mergetwoarray, and achieve good performance.

    import java.util.Queue;
    public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        if (lists.length == 1) return lists[0];
    
        Queue<ListNode> temp = new LinkedList<ListNode>();
        for (ListNode l: lists) {
            if (l != null)
                temp.add(l);
        }
    
        while (temp.size() > 1){
            ListNode l1 = temp.remove();
            ListNode l2 = temp.remove();
            temp.add(mergeTwoLists(l1, l2));
        }
    
        return temp.size() == 1 ? temp.remove() : null;
    }
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        if (l1 == null) return l2;
        if (l2 == null) return l1;
    
        ListNode head = new ListNode(0);
        ListNode index = head;
    
        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                index.next = l1;
                while (l1.next != null && l1.next.val < l2.val)
                    l1 = l1.next;
                index = l1;
                l1 = l1.next;
                //index.next = null;
            }else {
                index.next = l2;
                while (l2.next != null && l2.next.val < l1.val)
                    l2 = l2.next;
                index = l2;
                l2 = l2.next;
            }
        }
    
        if (l1 == null) index.next = l2;
        else index.next = l1;
    
        return head.next;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.