My 3ms Java solution with explanation, similar to the merge sort.


  • 2
    H
    public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int l = lists.length;
        if (l == 1)
            return lists[0];
        if (l == 0)
            return null;
        // divide the lists to two parts
        int l1 = l / 2;
        int l2 = l - l1;
        ListNode[] left = new ListNode[l1];
        ListNode[] right = new ListNode[l2];
        System.arraycopy(lists,0,left,0,l1); 
        System.arraycopy(lists,l1,right,0,l2); 
        ListNode p1 = mergeKLists(left);
        ListNode p2 = mergeKLists(right);
        ListNode head = null;
        // solve the null situation
        if (p1 == null) {
            head = p2;
            return head;
        }
        if (p2 == null) {
            head = p1;
            return head;
        }
        // determine the head node
        if (p1.val < p2.val) {
            head = p1;
            p1 = p1.next;
        } else {
            head = p2;
            p2 = p2.next;
        }
        ListNode p = head;
        // loop until one part become null
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            }
            else {
                p.next = p2;
                p2 = p2.next;
                p = p.next;
            }
        }
        // connect the remains to the list
        if (p1 == null)
            p.next = p2;
        else p.next = p1;
        return head;
    }
    }

  • 0

    张口就来3ms也是醉了...


Log in to reply
 

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