Merge Two Sorted Lists Cont…

Question: Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

You may check out the full question here. And in case this is your first time trying out this question, I would highly recommend you to start off from this post.

Approach 2: Starting from where we had left off. The naive approach simply involved building the new list by picking the smallest value from the two parent lists. Since, the parent lists are already sorted, all we need to check are the values at the head of the two lists, compare these two, and pick the smaller one.

When one of the lists get exhausted (considering that the lists are of unequal lengths), then only pick the values from the non-empty list.

The next approach we have here is heavily dependent on this first solution, plus the following —

• Leverage on the fact that the parent lists are in the form of LinkedLists.
• This can help us eliminate the last few iterations when when one of the lists become null/empty.

//Approach 2
//Runtime: 5ms
//Memory usage: 41.5MB
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode output=null;
    if((l1!=null && l2!=null && l1.val<=l2.val) || (l1!=null && l2==null)) {
     output = new ListNode(l1.val);
              l1 = l1.next;
    } else if(l2!=null){
     output = new ListNode(l2.val);
              l2 = l2.next;
    }
        ListNode previousNode = output;
   while(l1!=null && l2!=null) {
    if(l1.val<=l2.val) {
                      previousNode.next = new ListNode(l1.val);
                      l1 = l1.next;
                 } else {
                      previousNode.next = new ListNode(l2.val);  
                      l2 = l2.next;
                 }
    previousNode = previousNode.next;
        }
        if(l1!=null){
            previousNode.next = l1;
        } else if(l2!=null){
            previousNode.next=l2;
        }
   return output;
    }
}

Although the RunTime has improved, the memory usage still is excessive. May be save that for a future post? Until then…

Find more posts here.

Cheers & Chao!