# In-place merge two sorted linked lists without modifying links of the first list

Given two sorted linked lists, merge them without using extra space and without modifying links of the first list. The solution should preserve the sorted order of elements in both lists.

If m and n are the number of nodes in the first and second list respectively, then the first m smallest nodes in both lists combined should become part of the first list and the remaining nodes should become part of the second list. For example,

Input:

First List : 2 -> 6 -> 9 -> 10 -> 15 -> NULL
Second List: 1 -> 4 -> 5 -> 20 -> NULL

Output:

First List : 1 -> 2 -> 4 -> 5 -> 6 -> NULL
Second List: 9 -> 10 -> 15 -> 20 -> NULL

Simple solution is to use merge procedure of the merge-sort algorithm to merge both lists. After merging both lists, we assign first m smallest nodes to the first linked list and the remaining n nodes to the second linked list where m and n are number of elements in the first and second linked list respectively. This can be done in O(m + n) time and constant space.

Above solution violates the problem constraints where we’re not allowed to modify links of the first list. However, there is no restriction on swapping data between the linked list nodes. The idea is to compare each node of the first list with head node of the second list and swap their data if current node of the first list is greater than the head node of the second list. The first list remains sorted with this data exchange, but sorted order for the second list might be disturbed. To fix it, we pop the front node from second list and insert it at its correct place in the sorted second list using SortedInsert() function. This is demonstrated below in C:

Output:

Before Merging::

First List :  2 ->  6 ->  9 -> 10 -> 15 -> NULL
Second List:  1 ->  4 ->  5 -> 20 -> NULL

After Merging::

First List :  1 ->  2 ->  4 ->  5 -> 6 -> NULL
Second List: 9 -> 10 -> 15 -> 20 -> NULL

The worst case time complexity of above solution is O(mn) where m and n are the number of nodes in the first and second list respectively. The merging is done in-place but for each node in the first list, we might end up traversing the complete second list. This account for O(mn) time complexity.

The best case time complexity of above solution is O(m). The best case happens when both lists are already merged in sorted order and sortedInsert() method is never called which runs in O(n) time.

(1 votes, average: 5.00 out of 5)