Write a program to combine two sorted lists in Python

Problem: Given two sorted lists of N and M nodes respectively. Your task is to combine two lists together and return the combined list in standard order.

For example:

Input: a: 5->10->15, b: 2->3->20 Output: 2->3->5->10->15->20 Input: a: 1->1, b: 2->4 Output: 1->1->2->4

In this article, TipsMake.com will learn how to write a program to combine two sorted lists using Python and C++.

Method 1: Use fake buttons

The idea of ​​this method is to use a temporary dummy node as the first node of the resulting list. The Tail pointer always points to the last node in the resulting list so adding new nodes becomes much easier.

You can see the diagram below to make it easier to visualize:

Follow these steps to resolve the issue:

1. First, create a dummy node for the merged results list.
2. Now, create two pointers, one will point to list 1 (list1) and the other pointer to list 2 (list2).
3. Now, traverse both lists until they run out of all nodes.
4. If the value of a node being pointed to in one list is smaller than the value being pointed to in the other list, add that node to the merged results list and increment that pointer.

Here is sample code in Python language for your reference:

""" Python program to merge two sorted linked lists """ # Linked List Node class Node: def __init__(self, data): self.data = data self.next = None # Create & Handle List operations class LinkedList: def __init__(self): self.head = None # Method to display the list def printList(self): temp = self.head while temp: print(temp.data, end=" ") temp = temp.next # Method to add element to list def addToList(self, newData): newNode = Node(newData) if self.head is None: self.head = newNode return last = self.head while last.next: last = last.next last.next = newNode # Function to merge the lists # Takes two lists which are sorted # joins them to get a single sorted list def mergeLists(headA, headB): # A dummy node to store the result dummyNode = Node(0) # Tail stores the last node tail = dummyNode while True: # If any of the list gets completely empty # directly join all the elements of the other list if headA is None: tail.next = headB break if headB is None: tail.next = headA break # Compare the data of the lists and whichever is smaller is # appended to the last of the merged list and the head is changed if headA.data <= headB.data: tail.next = headA headA = headA.next else: tail.next = headB headB = headB.next # Advance the tail tail = tail.next # Returns the head of the merged list return dummyNode.next # Create 2 lists listA = LinkedList() listB = LinkedList() # Add elements to the list in sorted order listA.addToList(5) listA.addToList(10) listA.addToList(15) listB.addToList(2) listB.addToList(3) listB.addToList(20) # Call the merge function listA.head = mergeLists(listA.head, listB.head) # Display merged list print("Danh sách sau khi kết hợp là:") listA.printList() """ This code is contributed by Debidutta Rath """

Sample code in C++:

/* C++ program to merge two sorted linked lists */ #include using namespace std; /* Link list node */ class Node { public: int data; Node* next; }; /* pull off the front node of the source and put it in dest */ void MoveNode(Node** destRef, Node** sourceRef); /* Takes two lists sorted in increasing order, and splices their nodes together to make one big sorted list which is returned. */ Node* SortedMerge(Node* a, Node* b) { /* a dummy first node to hang the result on */ Node dummy; /* tail points to the last result node */ Node* tail = &dummy; /* so tail->next is the place to add new nodes to the result. */ dummy.next = NULL; while (1) { if (a == NULL) { /* if either list runs out, use the other list */ 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); } /* UTILITY FUNCTIONS */ /* MoveNode() function takes the node from the front of the source, and move it to the front of the dest. It is an error to call this with the source list empty. Before calling MoveNode(): source == {1, 2, 3} dest == {1, 2, 3} After calling MoveNode(): source == {2, 3} dest == {1, 1, 2, 3} */ void MoveNode(Node** destRef, Node** sourceRef) { /* the front source node */ Node* newNode = *sourceRef; assert(newNode != NULL); /* Advance the source pointer */ *sourceRef = newNode->next; /* Link the old dest off the new node */ newNode->next = *destRef; /* Move dest to point to the new node */ *destRef = newNode; } /* Function to insert a node at the beginning of the linked list */ void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } /* Driver code*/ int main() { /* Start with the empty list */ Node* res = NULL; Node* a = NULL; Node* b = NULL; /* Let us create two sorted linked lists to test the functions Created lists, a: 5->10->15, b: 2->3->20 */ push(&a, 15); push(&a, 10); push(&a, 5); push(&b, 20); push(&b, 3); push(&b, 2); /* Remove duplicates from linked list */ res = SortedMerge(a, b); cout << "Danh sách sau khi kết hợp là: n"; printList(res); return 0; } // This code is contributed by rathbhupendra 

The returned result is:

Danh sách sau khi kết hợp là: 2 3 5 10 15 20 

Method 2: Use recursion

The idea of ​​this approach is to move forward with a node in recursion having a smaller node value. When any node ends, append the rest of the already linked list.

Follow these steps to resolve the issue:

1. Create a function that takes two pointers to the list to be passed in.
2. Then check to see which of the two nodes passed in has the smaller value.
3. The node with the smaller value executes the instruction recursively by moving forward with the red pointer and concurrently concatenating the recursive instruction to the node.
4. Also set two base cases to check if one of the lists has reached the value of NULL and then concatenate the rest of the linked list.

Here is the sample code for your reference:

# Python3 program merge two sorted linked # in third linked list using recursive. # Node class class Node: def __init__(self, data): self.data = data self.next = None # Constructor to initialize the node object class LinkedList: # Function to initialize head def __init__(self): self.head = None # Method to print linked list def printList(self): temp = self.head while temp: print(temp.data, end=" ") temp = temp.next # Function to add of node at the end. def append(self, new_data): new_node = Node(new_data) if self.head is None: self.head = new_node return last = self.head while last.next: last = last.next last.next = new_node # Function to merge two sorted linked list. def mergeLists(head1, head2): # create a temp node NULL temp = None # List1 is empty then return List2 if head1 is None: return head2 # if List2 is empty then return List1 if head2 is None: return head1 # If List1's data is smaller or # equal to List2's data if head1.data <= head2.data: # assign temp to List1's data temp = head1 # Again check List1's data is smaller or equal List2's # data and call mergeLists function. temp.next = mergeLists(head1.next, head2) else: # If List2's data is greater than or equal List1's # data assign temp to head2 temp = head2 # Again check List2's data is greater or equal List's # data and call mergeLists function. temp.next = mergeLists(head1, head2.next) # return the temp list. return temp # Driver Function if __name__ == '__main__': # Create linked list : list1 = LinkedList() list1.append(5) list1.append(10) list1.append(15) # Create linked list 2 : list2 = LinkedList() list2.append(2) list2.append(3) list2.append(20) # Create linked list 3 list3 = LinkedList() # Merging linked list 1 and linked list 2 # in linked list 3 list3.head = mergeLists(list1.head, list2.head) print("Danh sách sau khi kết hợp là:") list3.printList() # This code is contributed by 'Shriaknt13'.

Sample code in C++:

/* C++ program to merge two sorted linked lists */ #include using namespace std; /* Link list node */ class Node { public: int data; Node* next; }; /* pull off the front node of the source and put it in dest */ void MoveNode(Node** destRef, Node** sourceRef); /* Takes two lists sorted in increasing order, and splices their nodes together to make one big sorted list which is returned. */ Node* SortedMerge(Node* a, Node* b) { Node* result = NULL; /* Base cases */ if (a == NULL) return (b); else if (b == NULL) 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); } /* UTILITY FUNCTIONS */ /* MoveNode() function takes the node from the front of the source, and move it to the front of the dest. It is an error to call this with the source list empty. Before calling MoveNode(): source == {1, 2, 3} dest == {1, 2, 3} After calling MoveNode(): source == {2, 3} dest == {1, 1, 2, 3} */ void MoveNode(Node** destRef, Node** sourceRef) { /* the front source node */ Node* newNode = *sourceRef; assert(newNode != NULL); /* Advance the source pointer */ *sourceRef = newNode->next; /* Link the old dest off the new node */ newNode->next = *destRef; /* Move dest to point to the new node */ *destRef = newNode; } /* Function to insert a node at the beginning of the linked list */ void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given linked list */ void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } /* Driver code*/ int main() { /* Start with the empty list */ Node* res = NULL; Node* a = NULL; Node* b = NULL; /* Let us create two sorted linked lists to test the functions Created lists, a: 5->10->15, b: 2->3->20 */ push(&a, 15); push(&a, 10); push(&a, 5); push(&b, 20); push(&b, 3); push(&b, 2); /* Remove duplicates from linked list */ res = SortedMerge(a, b); cout << "Danh sách sau khi kết hợp là: n"; printList(res); return 0; } // This code is contributed by rathbhupendra 

The returned result is:

Danh sách sau khi kết hợp là: 2 3 5 10 15 20 

Method 3: Using reverse list method with C++ language

The idea of ​​this method is to first reverse both given lists and then traverse both lists from beginning to end and compare the nodes of the two lists. Next, insert the node with the greater value at the top of the resulting list. In this way we will get the list of results in ascending order.

Follow these steps to resolve the issue:

1. Initialize the resulting list to be empty: head = NULL.
2. Let "a" and "b" be the beginning of the first list and the second list respectively.
3. Reverse both lists.
4. When (a !=NULL and b!=NULL):
   1. Find the greater of both (current "a" and "b" values).
   2. Insert the larger value of the button in front of the result list.
   3. Continue with the larger buttons in the list.
5. If "b" becomes NULL before "a", insert all nodes of "a" into the resulting list from the beginning.
6. If "a" becomes NULL before "b", insert all nodes of "b" into the resulting list at the beginning.

Here is sample code in C++ for your reference:

/*Given two sorted linked lists consisting of N and M nodes respectively. The task is to merge both of the list (in-place) and return head of the merged list.*/ #include using namespace std; /* Link list Node */ struct Node { int key; struct Node* next; }; // Function to reverse a given Linked List using Recursion Node* reverseList(Node* head) { if (head->next == NULL) return head; Node* rest = reverseList(head->next); head->next->next = head; head->next = NULL; return rest; } // Given two non-empty linked lists 'a' and 'b' Node* sortedMerge(Node* a, Node* b) { // Reverse Linked List 'a' a = reverseList(a); // Reverse Linked List 'b' b = reverseList(b); // Initialize head of resultant list Node* head = NULL; Node* temp; // Traverse both lists while both of them // have nodes. while (a != NULL && b != NULL) { // If a's current value is greater than or equal to // b's current value. if (a->key >= b->key) { // Store next of current Node in first list temp = a->next; // Add 'a' at the front of resultant list a->next = head; // Make 'a' - head of the result list head = a; // Move ahead in first list a = temp; } // If b's value is greater. Below steps are similar // to above (Only 'a' is replaced with 'b') else { temp = b->next; b->next = head; head = b; b = temp; } } // If second list reached end, but first list has // nodes. Add remaining nodes of first list at the // beginning of result list while (a != NULL) { temp = a->next; a->next = head; head = a; a = temp; } // If first list reached end, but second list has // nodes. Add remaining nodes of second list at the // beginning of result list while (b != NULL) { temp = b->next; b->next = head; head = b; b = temp; } // Return the head of the result list return head; } /* Function to print Nodes in a given linked list */ void printList(struct Node* Node) { while (Node != NULL) { cout << Node->key << " "; Node = Node->next; } } /* Utility function to create a new node with given key */ Node* newNode(int key) { Node* temp = new Node; temp->key = key; temp->next = NULL; return temp; } /* Driver program to test above functions*/ int main() { /* Start with the empty list */ struct Node* res = NULL; /* Let us create two sorted linked lists to test the above functions. Created lists shall be a: 5->10->15->40 b: 2->3->20 */ Node* a = newNode(5); a->next = newNode(10); a->next->next = newNode(15); a->next->next->next = newNode(40); Node* b = newNode(2); b->next = newNode(3); b->next->next = newNode(20); /* merge 2 sorted Linked Lists */ res = sortedMerge(a, b); cout << "Danh sách sau khi kết hợp là: " << endl; printList(res); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) 

The returned result is:

Danh sách sau khi kết hợp là: 2 3 5 10 15 20 

TipsMake.com hope this article will be useful to you.

Jessica Tanner

Update 27 June 2023