Merge two sorted linked lists into one
Write a function that takes two lists, each of which is sorted in increasing order, and merges the two into a single list in increasing order, and returns it.
For example, consider lists a = {1, 3, 5, 7} and b = {2, 4, 6}. Merging them should yield the list {1, 2, 3, 4, 5, 6, 7}.
The problem can be solved either iteratively or recursively. There are many cases to deal with – either a or b may be empty during processing, either a or b can run out first, and finally, there’s the problem of starting the result list empty, and building it up while going through a and b.
1. Using Dummy Nodes
The strategy here uses a temporary dummy node as the start of the result list. The pointer tail always points to the last node in the result list, so appending new nodes is easy. The dummy node gives the tail something to point to initially when the result list is empty. This dummy node is efficient since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either a or b and adding it at the tail. When we are done, the result is in dummy.next.
Following is the C, Java, and Python implementation of the idea:
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 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL\n"); } // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = *head; *head = newNode; } // Function takes the node from the front of the source and moves it // to the front of the destination void moveNode(struct Node** destRef, struct Node** sourceRef) { // if the source list empty, do nothing if (*sourceRef == NULL) { return; } struct Node* newNode = *sourceRef; // the front source node *sourceRef = (*sourceRef)->next; // advance the source pointer newNode->next = *destRef; // link the old dest off the new node *destRef = newNode; // move dest to point to the new node } // Takes two lists sorted in increasing order and merge their nodes // to make one big sorted list, which is returned struct Node* sortedMerge(struct Node* a, struct Node* b) { // a dummy first node to hang the result on struct Node dummy; dummy.next = NULL; // points to the last result node — so `tail->next` is the place // to add new nodes to the result. struct Node* tail = &dummy; while (1) { // if either list runs out, use the other list if (a == NULL) { tail->next = b; break; } else if (b == NULL) { tail->next = a; break; } if (a->data <= b->data) { moveNode(&(tail->next), &a); } else { moveNode(&(tail->next), &b); } tail = tail->next; } return dummy.next; } int main(void) { // input keys int keys[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(keys)/sizeof(keys[0]); struct Node *a = NULL, *b = NULL; for (int i = n - 1; i >= 0; i = i - 2) { push(&a, keys[i]); } for (int i = n - 2; i >= 0; i = i - 2) { push(&b, keys[i]); } // print both lists printf("First List: "); printList(a); printf("Second List: "); printList(b); struct Node* head = sortedMerge(a, b); printf("After Merge: "); printList(head); return 0; } |
Output:
First List: 1 —> 3 —> 5 —> 7 —> NULL
Second List: 2 —> 4 —> 6 —> NULL
After Merge: 1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> NULL
Java
|
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 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } Node() {} } class Main { // Helper function to print a given linked list public static void printList(String msg, Node head) { System.out.print(msg); Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Takes two lists sorted in increasing order and merge their nodes // to make one big sorted list, which is returned public static Node sortedMerge(Node a, Node b) { // a dummy first node to hang the result on Node dummy = new Node(); // points to the last result node — so `tail.next` is the place // to add new nodes to the result. Node tail = dummy; while (true) { // if either list runs out, use the other list if (a == null) { tail.next = b; break; } else if (b == null) { tail.next = a; break; } if (a.data <= b.data) { if (a != null) { Node newNode = a; a = a.next; newNode.next = tail.next; tail.next = newNode; } } else { if (b != null) { Node newNode = b; b = b.next; newNode.next = tail.next; tail.next = newNode; } } tail = tail.next; } return dummy.next; } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 3, 4, 5, 6, 7 }; Node a = null, b = null; for (int i = keys.length - 1; i >= 0; i = i - 2) { a = a = new Node(keys[i], a); } for (int i = keys.length - 2; i >= 0; i = i - 2) { b = b = new Node(keys[i], b); } // print both lists printList("First List: ", a); printList("Second List: ", b); Node head = sortedMerge(a, b); printList("After Merge: ", head); } } |
Output:
First List: 1 —> 3 —> 5 —> 7 —> null
Second List: 2 —> 4 —> 6 —> null
After Merge: 1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> null
Python
|
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 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Helper function to print a given linked list def printList(msg, head): print(msg, end='') ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Takes two lists sorted in increasing order and merge their nodes # to make one big sorted list, which is returned def sortedMerge(a, b): # a dummy first node to hang the result on dummy = Node() # points to the last result node — so `tail.next` is the place # to add new nodes to the result. tail = dummy while True: # if either list runs out, use the other list if a is None: tail.next = b break elif b is None: tail.next = a break if a.data <= b.data: if a: newNode = a # the front source node a = a.next # advance the source newNode.next = tail.next # link the old dest off the new node tail.next = newNode # move dest to point to the new node elif b: newNode = b # the front source node b = b.next # advance the source newNode.next = tail.next # link the old dest off the new node tail.next = newNode # move dest to point to the new node tail = tail.next return dummy.next if __name__ == '__main__': a = b = None for i in reversed(range(1, 8, 2)): a = Node(i, a) for i in reversed(range(2, 7, 2)): b = Node(i, b) # print both lists printList('First List: ', a) printList('Second List: ', b) head = sortedMerge(a, b) printList('After Merge: ', head) |
Output:
First List: 1 —> 3 —> 5 —> 7 —> None
Second List: 2 —> 4 —> 6 —> None
After Merge: 1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> None
2. Using Local References
This solution is structurally very similar to the above, but it avoids using a dummy node. Instead, it maintains a struct node** pointer, lastPtrRef, which always points to the last pointer of the result list. This solves the same case that the dummy node did – dealing with the result list when it is empty. When trying to build up a list at its tail, use either the dummy node or the struct node** “reference” strategy.
This approach is demonstrated below in C:
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 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL\n"); } // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = *head; *head = newNode; } // Function takes the node from the front of the source and moves it // to the front of the destination void moveNode(struct Node** destRef, struct Node** sourceRef) { // if the source list empty, do nothing if (*sourceRef == NULL) { return; } struct Node* newNode = *sourceRef; // the front source node *sourceRef = (*sourceRef)->next; // advance the source pointer newNode->next = *destRef; // link the old dest off the new node *destRef = newNode; // move dest to point to the new node } // Takes two lists sorted in increasing order and merge their nodes // to make one big sorted list, which is returned struct Node* sortedMerge(struct Node* a, struct Node* b) { struct Node* result = NULL; struct Node** lastPtrRef = &result; // point to the last result pointer while (1) { if (a == NULL) { *lastPtrRef = b; break; } else if (b == NULL) { *lastPtrRef = a; break; } if (a->data <= b->data) { moveNode(lastPtrRef, &a); } else { moveNode(lastPtrRef, &b); } // tricky: advance to point to the next `.next` field lastPtrRef = &((*lastPtrRef)->next); } return result; } int main(void) { // input keys int keys[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(keys)/sizeof(keys[0]); struct Node *a = NULL, *b = NULL; for (int i = n - 1; i >= 0; i = i - 2) { push(&a, keys[i]); } for (int i = n - 2; i >= 0; i = i - 2) { push(&b, keys[i]); } // print both lists printf("First List: "); printList(a); printf("Second List: "); printList(b); struct Node* head = sortedMerge(a, b); printf("After Merge: "); printList(head); return 0; } |
Output:
First List: 1 —> 3 —> 5 —> 7 —> NULL
Second List: 2 —> 4 —> 6 —> NULL
After Merge: 1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> NULL
3. Using Recursion
This is a nice problem where the recursive solution code is much cleaner than the iterative code. The recursive implementation can be seen below in C, Java, and Python:
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 |
#include <stdio.h> #include <stdlib.h> // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList(struct Node* head) { struct Node* ptr = head; while (ptr) { printf("%d —> ", ptr->data); ptr = ptr->next; } printf("NULL\n"); } // Helper function to insert a new node at the beginning of the linked list void push(struct Node** head, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = *head; *head = newNode; } // Takes two lists sorted in increasing order and merge their nodes // to make one big sorted list, which is returned struct Node* sortedMerge(struct Node* a, struct Node* b) { // base cases if (a == NULL) { return b; } else if (b == NULL) { return a; } struct Node* result = NULL; // pick either `a` or `b`, and recur if (a->data <= b->data) { result = a; result->next = sortedMerge(a->next, b); } else { result = b; result->next = sortedMerge(a, b->next); } return result; } int main(void) { // input keys int keys[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(keys)/sizeof(keys[0]); struct Node *a = NULL, *b = NULL; for (int i = n - 1; i >= 0; i = i - 2) { push(&a, keys[i]); } for (int i = n - 2; i >= 0; i = i - 2) { push(&b, keys[i]); } // print both lists printf("First List: "); printList(a); printf("Second List: "); printList(b); struct Node* head = sortedMerge(a, b); printf("After Merge: "); printList(head); return 0; } |
Output:
First List: 1 —> 3 —> 5 —> 7 —> NULL
Second List: 2 —> 4 —> 6 —> NULL
After Merge: 1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> NULL
Java
|
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 |
// A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } } class Main { // Helper function to print a given linked list public static void printList(String msg, Node head) { System.out.print(msg); Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Takes two lists sorted in increasing order and merge their nodes // to make one big sorted list, which is returned public static Node sortedMerge(Node a, Node b) { // base cases if (a == null) { return b; } else if (b == null) { return a; } Node result; // pick either `a` or `b`, and recur if (a.data <= b.data) { result = a; result.next = sortedMerge(a.next, b); } else { result = b; result.next = sortedMerge(a, b.next); } return result; } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 3, 4, 5, 6, 7 }; Node a = null, b = null; for (int i = keys.length - 1; i >= 0; i = i - 2) { a = new Node(keys[i], a); } for (int i = keys.length - 2; i >= 0; i = i - 2) { b = new Node(keys[i], b); } // print both lists printList("First List: ", a); printList("Second List: ", b); Node head = sortedMerge(a, b); printList("After Merge: ", head); } } |
Output:
First List: 1 —> 3 —> 5 —> 7 —> null
Second List: 2 —> 4 —> 6 —> null
After Merge: 1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> null
Python
|
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 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Helper function to print a given linked list def printList(msg, head): print(msg, end='') ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Takes two lists sorted in increasing order and merge their nodes # to make one big sorted list, which is returned def sortedMerge(a, b): # base cases if a is None: return b elif b is None: return a # pick either `a` or `b`, and recur if a.data <= b.data: result = a result.next = sortedMerge(a.next, b) else: result = b result.next = sortedMerge(a, b.next) return result if __name__ == '__main__': # input keys keys = [1, 2, 3, 4, 5, 6, 7] a = b = None for i in reversed(range(0, len(keys), 2)): a = Node(keys[i], a) for i in reversed(range(1, len(keys), 2)): b = Node(keys[i], b) # print both lists printList('First List: ', a) printList('Second List: ', b) head = sortedMerge(a, b) printList('After Merge: ', head) |
Output:
First List: 1 —> 3 —> 5 —> 7 —> None
Second List: 2 —> 4 —> 6 —> None
After Merge: 1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> None
The time complexity of all above-discussed methods is O(m + n), where m and n are the total number of nodes in the first and second list, respectively. The iterative version doesn’t require any extra space, whereas the recursive version uses stack space proportional to the lists’ length.
Source: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)