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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
#include <stdio.h> #include <stdlib.h> // Data Structure to store a linked list node struct Node { int data; struct Node *next; }; // Helper function to create a new node of the linked list struct Node *newNode(int data) { struct Node *newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; return newNode; } // Helper function to print given linked list void printList(char *msg, struct Node *head) { printf("%s", msg); while (head) { printf("%2d -> ", head->data); head = head->next; } printf("NULL\n"); } // Function to insert the given node into the correct sorted position in // the given list sorted in increasing order void sortedInsert(struct Node** head, struct Node *newNode) { // Special case for the head end if (*head == NULL || (*head)->data >= newNode->data) { newNode->next = *head; *head = newNode; return; } // Locate the node before the point of insertion struct Node *current = *head; while (current->next != NULL && current->next->data < newNode->data) { current = current->next; } newNode->next = current->next; current->next = newNode; } // Function to exchange data of given linked list nodes void swapData(struct Node *first, struct Node *second) { int data = first->data; first->data = second->data; second->data = data; } // Function to in-place merge two sorted linked lists without // modifying links of the first list. // Note that second list is a "reference" pointer to the head node // whereas first list is just an copy of the head node void mergeLists(struct Node *first, struct Node** second) { // loop till either list runs out while (first && *second) { // compare each element of the first list with the first element // of second list if (first->data > (*second)->data) { // exchange data if current node of the first list has more value // than the first node of the second list swapData(first, *second); // pop front node from the second list struct Node *front = *second; *second = (*second)->next; // insert front node at its correct place in the second list sortedInsert(second, front); } // advance first list to the next node first = first->next; } } // main function int main(void) { // construct first list struct Node *first = newNode(2); first->next = newNode(6); first->next->next = newNode(9); first->next->next->next = newNode(10); first->next->next->next->next = newNode(15); // construct second list struct Node *second = newNode(1); second->next = newNode(4); second->next->next = newNode(5); second->next->next->next = newNode(20); // print both lists before merge printf("Before Merging::\n\n"); printList("First List : ", first); printList("Second List: ", second); // merge both lists mergeLists(first, &second); // print both lists after merge printf("\n\nAfter Merging::\n\n"); printList("First List : ", first); printList("Second List: ", second); return 0; } |

`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.

**Author:** Aditya Goel

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply