Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
Write a SortedMerge() function that takes two lists, each sorted in ascending order, and then merges the two lists into a single ascending list. SortedMerge() should return a new list. A new list should be made by stitching together the nodes of the first two lists.
For example, if the first list A is 5->10->15 and the other list B is 2->3->20, SortedMerge() should return a pointer 3->5->10->15->20 to the head of the merged list 2->.
There are many cases to deal with: A or B may be empty, a or B may run out first during processing, and finally the result list starts empty, building up the problem that it goes up as it goes through ‘a’ and ‘b’.
Method one (using virtual nodes) The policy here uses the temporary virtual node as the beginning of the result list. The Tail pointer always points to the last node in the result list, so adding a new node is easy.
When the result list is empty, the virtual node provides the initial pointing object for the tail. This virtual node is valid because it is only temporary and allocated in the stack. The loop continues, removing a node from “A” or “b” and adding it to the end. When we’re done, the results are in dummy.next.
Here is an implementation of the above method:
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node* next;
};
Node* SortedMerge(Node* a, Node* b)
{
Node dummy;
Node* tail = &dummy;
dummy.next = NULL;
while (1)
{
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);
}
void MoveNode(Node** destRef, Node** sourceRef)
{
Node* newNode = *sourceRef;
assert(newNode ! =NULL);
*sourceRef = newNode->next;
newNode->next = *destRef;
*destRef = newNode;
}
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node(a); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; }void printList(Node *node)
{
while(node! =NULL)
{
cout<<node->data<<""; node = node->next; }}int main(a)
{
Node* res = NULL;
Node* a = NULL;
Node* b = NULL;
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&b, 20);
push(&b, 3);
push(&b, 2);
res = SortedMerge(a, b);
cout << "Merged Linked List is: \n";
printList(res);
return 0;
}
Copy the codeOutput:
Merged Linked List is:
2 3 5 10 15 20
Copy the codeApproach 2 (using local references)
This solution is very similar in structure, but it avoids the use of virtual nodes. Instead, it maintains a struct node** pointer, lastPtrRef, which always points to the last pointer in the result list. This addresses the same situation as with virtual nodes — processing it when the result list is empty. If you are trying to build a list at the end of it, you can use a virtual node or structural node ** “reference” strategy (see Section 1 for more information).
Node* SortedMerge(Node* a, Node* b)
{
Node* result = NULL;
Node** lastPtrRef = &result;
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);
}
lastPtrRef = &((*lastPtrRef)->next);
}
return(result);
}
Copy the codeMethod 3 (using recursion)
Merge is one of those great recursive problems where the recursive solution code is much cleaner than the iterative code. However, you may not want to use the recursive version for production code because it will use stack space proportional to the length of the list.
Node* SortedMerge(Node* a, Node* b)
{
Node* result = NULL;
if (a == NULL)
return(b);
else if (b == NULL)
return(a);
if (a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}
Copy the codeTime complexity: Because we walked through both lists completely. Thus, the time complexity is O(m+n), where m and n are the lengths of the two lists to be merged.
Approach 4 (Reverse the list)
The idea involves first reversing the given list, then iterating through the two lists to the end, then comparing the nodes of the two lists, and inserting the node with the larger value at the beginning of the resulting list. In this way, we get the list of results in ascending order.
1) Initialize the result list to NULL: head = NULL. 2) Make 'a' and 'b' the heads of the first and second lists, respectively. 3) Reverse the two lists. 4) While (a ! = NULL and b ! = NULL) a) finds the larger of the two (currently 'a' and 'b') b) inserts the larger value of the node in front of the result list. C) Move forward in the larger node list. 5) If 'b' becomes NULL before 'a', all nodes of 'a' are inserted at the beginning of the result list. 6) If 'a' becomes NULL before 'b', all nodes of 'b' are inserted at the beginning of the result list.Copy the codeThe following is an implementation of the above solution.
#include <iostream>
using namespace std;
struct Node {
int key;
struct Node* next;
};
Node* reverseList(Node* head)
{
if (head->next == NULL)
return head;
Node* rest = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return rest;
}
Node* sortedMerge(Node* a, Node* b)
{
a = reverseList(a);
b = reverseList(b);
Node* head = NULL;
Node* temp;
while(a ! =NULL&& b ! =NULL) {
if (a->key >= b->key) {
temp = a->next;
a->next = head;
head = a;
a = temp;
}
else{ temp = b->next; b->next = head; head = b; b = temp; }}while(a ! =NULL) {
temp = a->next;
a->next = head;
head = a;
a = temp;
}
while(b ! =NULL) {
temp = b->next;
b->next = head;
head = b;
b = temp;
}
return head;
}
void printList(struct Node* Node)
{
while(Node ! =NULL) {
cout << Node->key << ""; Node = Node->next; }}Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
int main(a)
{
struct Node* res = NULL;
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);
cout << "List A before merge: \n";
printList(a);
cout << "\nList B before merge: \n";
printList(b);
res = sortedMerge(a, b);
cout << "\nMerged Linked List is: \n";
printList(res);
return 0;
}
Copy the codeOutput:
List A before merge:
5 10 15 40
List B before merge:
2 3 20
Merged Linked List is:
2 3 5 10 15 20 40
Copy the codeTime complexity: Because we walked through both lists completely. Thus, the time complexity is O(m+n), where m and n are the lengths of the two lists to be merged.
🥇 past quality articles
Singly linked list data structure of the chain table from the introduction of | first set of singly linked list data structure linked list and array | second singly linked list data structure of chain table insert | | delete nodes of the third set of singly linked list data structure of the fourth set of singly linked list data structure to delete a given location linked list node | the fifth set Singly linked list data structure of the check method of array and list | singly linked list data structure of the set of 6-1 check method of array and list | set 6-2 singly linked list data structure of the length of the chain table lookup (iteration and recursion) | 7 sets of singly linked list data structure of switching nodes in the list without exchanging data | 8 sets Singly linked list data structure of the inversion list | 9 sets
📣 Endnote: For more information on data structures, you can follow me: Haiyong, I hope you found this article helpful.
If you see this, thank you for reading 🙂
💌 welcomes your comments and suggestions in the comments section! 💌
If you really learn something new from this article, like it, bookmark it and share it with your friends. 🤗 and finally, don’t forget ❤ or 📑.