criskgl
9/25/2019 - 9:20 AM

Merge two sorted lists

Merge two sorted lists

WITHOUT STORING ELEMENTS IN AUXILIAR STRUCTURE

The idea is simple:

-we create a "prev" node -we save a pointer to first prev called "prevHead"

from here we iterate doing the following:

  • Set prev.next to node that has smallest value of current L1 node or current L2 node
  • Move pointer in L1//L2(whichever had the smallest) to next element
  • We ALWAYS move prev pointer one step after connecting prev to node with smallest value of the two lists

Once the iteration finishes one of the two lists has been fully gone through.

  • Concatenate prev to node pointed in list that has not been fully covered yet.

FINISHED!! 😄

mergeTwoSortedLists.java
content_copyfile_download
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //edge cases
    if(l1 == null && l2 == null) return l1;
    ListNode prev = new ListNode(-1);//start as a prehead
    ListNode prevHead = prev;
    while(l1 != null & l2 != null){//While there are nodes in both lists
        if(l1.val <= l2.val){
            prev.next = l1;
            l1 = l1.next;
        }else{
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }
    // at least one of the lists will be left with node/s.
    //we just append whats left of l1 or l2 to prev.
    if(l1 == null){//append list 2
        prev.next = l2;
    }else{//append list 1
        prev.next = l1;
    }
    return prevHead.next;
}