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: