Merge two sorted linked lists
It is strongly recommended to do merging in-place using O(1) extra space.
Algorithm:
- Base case : If any one of list is empty return node empty list head
- Here we will add all node from list2 to list 1
- Iterate till
node2 != null
- Get position for node2 in list1
- Create a temporary node with node2 and add this node in list1 at above said position
- Move node2 pointer to next element in list2
- Return list1 head
Latest Source Code:
Github: InPlaceSortedListMerger.java
Output:
3 8 12 18 6 9 10 30 39 40 3 6 8 9 10 12 18 30 39 40