Merge two sorted linked lists

Merge two sorted linked lists

Given two linked lists sorted in ascending order.

Merge them in-place and return head of the merged list. For example, if first list is 4->8->12 and second list is 3->6, then the result list should be 3->4->6->8->12.

It is strongly recommended to do merging in-place using O(1) extra space.

Non-Recursive Algorithm:

  • If any one of list is empty then return other non-empty
  • The logic here is, to add all nodes from list 2 to list 1 at their proper place
  • Repeat bellow tasks – till node2 is not null
  • There could be two possible case when either node1.data > node2.data or node1.data <= node2.data
  • If node1.data < node2.data, then move list 1 till we find node1.next == null or node1.next.data < node2.data
  • Then add node2 at that position and update next pointer properly
  • If node1.data >= node2.data, then add node2 in front of list 1 and change pointer properly

Recursive Algorithm:

  • Base case – If any one of list is empty then return other non-empty
  • If node1.data <= node2.data then, set node1.next pointer with recursive call with node1.next and node2
  • If node1.data > node2.data then, set node2.next pointer with recursive call with node1 and node.next

Latest Source Code:
Github: SortedListMerger.java


Output:

2 5 16 17 
3 7 26 
2 3 5 7 16 17 26 
2 5 16 17 
3 7 26 
2 3 5 7 16 17 26 

Author: Hrishikesh Mishra