1ms Java Solution with clear explanation


  • 1

    Hard to explain in words, just see the below diagram:

    Two lists are:

    1->3->4->6
    2->5->7->8

    Cause 1<2, so pick current list be (1)->3->4->6, other list to be (2)->5->7->8 (note that the current node is enclosed by '()').

    1) 1<2, current list: 1->(3)->4->6, other list: (2)->5->7->8
    2) 3>2, current list: 1->2->(5)->7->8, other list: (3)->4->6
    4) 5>3, current list: 1->2->3->(4)->6, other list: (5)->7->8
    6) 4<5, current list: 1->2->3->4->(6), other list: (5)->7->8
    7) 6>5, current list: 1->2->3->4->5->(7)->8, other list: (6)
    8) 7>6, current list: 1->2->3->4->5->6->(), other list: (7)->8
    9) combine current list with other list: 1->2->3->4->5->6->7->8
    

    Note that for current list, we need to keep two references: pre and curr

     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        ListNode head = l1.val<=l2.val ? l1 : l2;
        ListNode pre = head;  // previous node of final list
        ListNode curr = pre.next;  // current node of final list
        ListNode other = l1==head ? l2 : l1;  // list other than head
        while(curr!=null) {
            if(curr.val<=other.val) {
                pre = curr;
                curr = curr.next;
            } else {
                pre.next = other;
                pre = other;
                other = curr;
                curr = pre.next;
            }
        }
        pre.next = other;
        return head;
    }

Log in to reply
 

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