## Merge two sorted linked lists

Problem statement is simple : Merge two sorted linked lists, without using extra space. To refer to the basics of linked list, please follow the post : Linked list data structure. This problem is commonly asked in telephonic round of Amazon and Microsoft. Let’s take an example and understand what is required as solution. Given two linked lists as following,

Result should be like this:

### Merge two sorted linked lists : Thoughts

Consider following two steps to merge sorted linked lists. First, figure out which node should be head of result list. Compare head nodes of two give lists, which ever is smaller, that should be the head of result list.

Second, compare two nodes, one from each list and decide which should go next in result linked list. Advance the pointer to next node of the node which is added to result list.

As no new node is allocated during this merge, we have to make sure that all the references are maintained when nodes are added to merged linked list.

We can start with one list as merge list and add nodes from second list at appropriate place in that list. Let’s say `L1` is our merged list and we always compare node on `L2` to see if it should be placed in `L1` at current position. `L1` grows as more nodes are sorted in merge list.

We compare first two nodes `L1` and `L2`, and decide that `node(2)`

has to go in merged list as head. If it was head of `L2`, we would have swapped L1 and L2 heads and still `L1` will be head of merged list. Why? Because we want that `L1` always points to last node in merged list and `L1` to represent sorted merged list till this point and `L2` switches between two input lists.

As `L1` always points to the last node of merged linked list, next node to compare should be `L1.next` i.e `node(4)`

and `L2` i.e `node(3)`

.

As L1 follows the merged linked list, we will move `L1.next` to point node(3), however doing it directly will lead to lose of entire linked list following it. So we do it in four steps : store `L1` next as temp; link `L2` to `L1.next`; `L2` points to `temp` and then move `L1` to `L1.next`

Node temp = L1.next; L1.next = L2; L2 = temp; L1 = L1.next

Next nodes to be compared are node(5), which is `L1.next` and node(5) which is `L2`.

Of course `node(4)`

has to be added to merged linked list, what should we do? First save `L1.next` in temp, temp now points to `node(5)`

. Second, point `L1.next` to `L2`, point `L2` to temp, and at last, `L1` moves to `L1.next`. State of two sorted linked lists looks as follows.

By this time you must have noticed that `L1` and `L2` do not point to the one list all the time, `L1` always points to the last node of merged list and `L2` points to first node of separated list which needs to be merged.

Now, `L1.next` which is `node(7)`

and `L2` which is `node(5)`

will be compared.

`node(5)`

is to be added in merged sorted list. Again same set of steps. `L1.next` stored as temp, `L1.next` points to `L2` i.e. `node(5)`

and then `L2` points to temp i.e. `node(7)`

Again, `node(9)`

which is `L1.next` will be compared to `L2` i.e `node(7)`

. `L1.next` should point to `L2`. Final state will be as follows

At this point, `L1.next` i.e node(8) is less than `L2`, this is simple case, where we just move `L1` to `L1.next` and `L2` remains as is.

Next two nodes follow the same pattern and added to merged sorted linked list.

At this point, special condition occurs which is `L1.next` is null. In this case, point `L1.next` to `L2` and two linked lists are merged.

## Merge two sorted linked lists : Implementation

#include <stdio.h> #include <stdlib.h> typedef struct node{ int data; struct node *next; } Node; Node * createNode(int val){ Node * temp = (Node *)malloc(sizeof(Node)); if(temp){ temp->data = val; temp->next = NULL; } return temp; } /* This function inserts node at the head of linked list */ void push(Node **headRef, int data){ Node * newNode = createNode(data); newNode->next = *headRef; *headRef = newNode; } void printList(Node * head){ while(head){ printf("%d->" , head->data ); head = head->next; } printf("NULL"); printf("\n"); } Node * MergeLists(Node *list1, Node *list2) { if (!list1) return list2; if (!list2) return list1; Node *head; //Chosing head of merged list if (list1->data < list2->data) { head = list1; } else { head = list2; list2 = list1; list1 = head; } while(list1->next && list2) { if (list1->next->data > list2->data) { //Step 1. Save the next pointer Node *tmp = list1->next; //Step 2. Change next pointer to point L2 list1->next = list2; //Step 3. Move L2 to temp list2 = tmp; } //Step 4. Move L1 ahead list1 = list1->next; } if (!list1->next) list1->next = list2; return head; } int main(){ Node * L1 = NULL; Node * L2 = NULL; Node * result = NULL; int carry = 0 ; /* creating list 1 */ push(&L1,7); push(&L1,6); push(&L1,4); push(&L1,3); /* creating list 2 */ push(&L2,10); push(&L2,8); push(&L2,1); L1 = MergeLists(L1,L2); printList(L1); return 0; }

Complexity of this method to merge two sorted lists into one is O(n+m) where n and m are number of nodes in two sorted linked lists.

### Recursive implementation to merge two sorted linked lists

#include<stdlib.h> #include<stdio.h> typedef struct node{ int data; struct node *next; } Node; Node * mergeSort(Node *a, Node *b){ Node *result = NULL; if(a == NULL) return b; else if(b == NULL) return a; /* For the first node, we would set the result to either a or b */ if(a->data <= b->data){ result = a; /* Result's next will point to smaller one in lists starting at a->next and b */ result->next = mergeSort(a->next,b); } else { result = b; /*Result's next will point to smaller one in lists starting at a and b->next */ result->next = mergeSort(a,b->next); } return result; } Node * createNode(int val){ Node * temp = (Node *)malloc(sizeof(Node)); if(temp){ temp->data = val; temp->next = NULL; } return temp; } /* This function inserts node at the head of linked list */ void push(Node **headRef, int data){ Node * newNode = createNode(data); newNode->next = *headRef; *headRef = newNode; } void printList(Node * head){ while(head){ printf("%d->" , head->data ); head = head->next; } printf("NULL"); printf("\n"); } /* Driver program to run above code */ int main(){ Node * L1 = NULL; Node * L2 = NULL; Node * result = NULL; int carry = 0 ; /* creating list 1 */ push(&L1,7); push(&L1,6); push(&L1,4); push(&L1,3); /* creating list 2 */ push(&L2,10); push(&L2,8); push(&L2,1); L1 = mergeSort(L1,L2); printList(L1); return 0; }

Please share if there is something wrong or missing. If you want to take personalized coaching from our expert teachers, please signup for free demo class.