10) Merge Two Sorted Lists

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Explanation



L1 = 1->4

L2 = 2->3

Output = 1->2->3->4

Create a dummy node. 
ListNode dummy = new ListNode(0);
//dummy = 0->null;

Assign the dummy node to head
ListNode head = dumy;
//head = 0->null

//iteration first time
while(l1 != null && l2 != null)
{
  int val1 = l1.val;
  int val2 = l2.val;

  //val1 = 1
  //val2 = 2

  Since val1 < val2, it satisfies the first condition
  if(val1 <= val2)
  {
        ListNode newNode = new ListNode(val1);
	//newNode = 1->null
        
	head.next = newNode;
        //put this newNode into head.next, 
        //head = 0->1->null

        l1 = l1.next;
        //iterate the l1 (l1 = l1.next)
        //now the l1 holds the 4->null
  }
  else
  { ... 
  }

  head = head.next;
  //now head moves to the 1->null
}

//iteration second time
while(l1 != null && l2 != null)
{
  int val1 = l1.val;
  int val2 = l2.val;

  //val1 = 4
  //val2 = 2

  Since val1 > val2, it does not satisfies the first condition, it satisfies the else condition
  if(val1 <= val2)
  {
        ListNode newNode = new ListNode(val1);
	
	head.next = newNode;
       
        l1 = l1.next;
  }
  else
  {
	ListNode newNode = new ListNode(val2);
	//newNode = 2->null

        head.next = newNode;
        //head = 0->1->2->null

        l2 = l2.next; 
        //l2 = 3->null 
  }

  head = head.next;
  //now head moves to the 2->null
}


//iteration third time
while(l1 != null && l2 != null)
{
  int val1 = l1.val;
  int val2 = l2.val;

  //val1 = 4
  //val2 = 3

  Since val1 > val2, it does not satisfies the first condition, it satisfies the else condition
  if(val1 <= val2)
  {
        ListNode newNode = new ListNode(val1);
	
	head.next = newNode;
       
        l1 = l1.next;
  }
  else
  {
	ListNode newNode = new ListNode(val2);
	//newNode = 3->null

        head.next = newNode;
        //head = 0->1->2-3>null

        l2 = l2.next; 
        //l2 = null 
  }

  head = head.next;
  //now head moves to the 2->null
}

Since l2 is null, it comes out of the while loop
Still now we have, 
l1 = 4->null;
head = 0->1->2->3->null;
Important Note : head is standing in the 3->null

if(l1 == null) //since l1 is not null now, it will not satisfy this condition, it moves into else part
   head.next = l2.next;
else
   head.next = l1;
//head = 0->1->2->3->4-null;

Note: 
 head = 0->1->2->3->4->null;
 head pointer points to the 4->null;

 We already have dummy node pointer, it is already refering to the headth 0->... node,

 so when i return dummy.next - it will return 1-2->3->4->null; 

Here, we solved this problem.

Program

Provided Code


class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

Solution



class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode sentinel = new ListNode(0);
        ListNode head = sentinel;
        while(l1 != null && l2 != null)
        {
            int val1 = l1.val;
            int val2 = l2.val;
            
            if(val1 <= val2)
            {
                ListNode newNode = new ListNode(val1);
                head.next = newNode;
                l1 = l1.next;
            }
            else
            {
                ListNode newNode = new ListNode(val2);
                head.next = newNode;
                l2 = l2.next;
            }
            
            head = head.next;
        }
        if(l1 == null)
            head.next = l2;
        else
            head.next = l1;
        
        return sentinel.next;
    }
}

Time Complexity : O(n + m)

Space Complexity : O(1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s