Solution

• Create a new ListNode with dummy node as head, call it as result. We are going to attach input list's elements to this list and finally return answer by removing this dummy head.
• Create another temporary ListNode variable to hold the tail of the resultant list, so that next node comes in order from input lists will be attached to this.
  Initialize this with result from above step as that is the current tail.
• Run a while loop until both input lists are not null. Now check which node value is less among two input lists, add that to temp.next and move the pointer to next node for the list which has less value.
• At the end of while, move temp node to current tail. After adding a node from list1 or list2 to temp node, this will become the new tail as highlighted in line 35 in below code.
• Repeat this until either of the lists traversal reached to the end.
• Finally return result.next, this will remove the dummy head created in step 1 and return the rest.

public class MergeTwoSortedLists { static class ListNode { int element; ListNode next; public ListNode (int element) { this.element = element; } } public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode result = new ListNode(0);// create a new ListNode with a dummy head ListNode temp = result; // purpose of this temp List is to hold the tail of ListNode while (list1 != null || list2 != null) { if(list1 == null) { temp.next = list2; break; } if(list2 == null) { temp.next = list1; break; } if(list1.element <= list2.element) { temp.next = new ListNode(list1.element); list1 = list1.next; } else if (list1.element > list2.element) { temp.next = new ListNode(list2.element); list2 = list2.next; } temp = temp.next; // for the next iteration update the tail to current tail } return result.next; // return result by removing teh dummy head created in step-1 } }

Complexity Analysis:

Above code runs in O(m + n) time complexity where m is the size of the input list1 and n is the size of the input list2, as we are looping through the input lists only one time. Space complexity is O(n) that is taken by the result list.