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