/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
   static ListNode head = null;
        static ListNode last = null;
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
        
        ListNode tempHeadL2 = l2;
        ListNode tempHeadL1 = l1;

        if(tempHeadL1 == null && tempHeadL2 == null)
        {
            return null;
        }

        while(tempHeadL1 != null && tempHeadL2 != null)
        {
            if(tempHeadL1.val < tempHeadL2.val)
            {
                tempHeadL1 = moveSmallestNodeToHead(tempHeadL1); 
            }else{
                tempHeadL2 = moveSmallestNodeToHead(tempHeadL2); 
            }
        }

        while(tempHeadL1 == null && tempHeadL2 != null)
        {
            tempHeadL2 = moveSmallestNodeToHead(tempHeadL2);
        }

        while(tempHeadL1 != null && tempHeadL2 == null)
        {
            tempHeadL1 = moveSmallestNodeToHead(tempHeadL1);
        }

        return head;
    }
    
    
  static public ListNode moveSmallestNodeToHead(ListNode nodeToBeRemoved){
      
      // nodeToBeRemoved should not be null
      if(nodeToBeRemoved == null) return null;
      
      // reassign head to the next available node
      ListNode headOfListToRemoveFrom = nodeToBeRemoved.next;
     
      ListNode current = new ListNode();
      current.val = nodeToBeRemoved.val;
      current.next = null;
      
      if(head == null){
          head = current;
      }
      
      if (last != null) 
      {
          last.next = current;
      }
      
      last = current;
      
      return headOfListToRemoveFrom;
      
  }
    
}