Merging Two Sorted Linked Lists
To merge two sorted linked lists into a single sorted list, we can use a simple algorithm. We create a new list and iterate over the two input lists concurrently, comparing the elements and adding them to the new list in the sorted order.
Here's the C++ code for merging two sorted linked lists:
SNIPPET
1#include <iostream>
2using namespace std;
3
4// Linked List Node
5struct Node {
6 int data;
7 Node* next;
8 Node(int d) : data(d), next(nullptr) {}
9};
10
11// Function to merge two sorted linked lists
12Node* mergeLinkedLists(Node* head1, Node* head2) {
13 // Create a dummy node to store the merged list
14 Node* dummy = new Node(0);
15 Node* tail = dummy;
16
17 // Merge the two lists
18 while (head1 && head2) {
19 if (head1->data <= head2->data) {
20 tail->next = head1;
21 head1 = head1->next;
22 } else {
23 tail->next = head2;
24 head2 = head2->next;
25 }
26 tail = tail->next;
27 }
28
29 // Append any remaining nodes of the first list
30 if (head1) {
31 tail->next = head1;
32 }
33
34 // Append any remaining nodes of the second list
35 if (head2) {
36 tail->next = head2;
37 }
38
39 // Return the merged list
40 return dummy->next;
41}
42
43int main() {
44 // Create two sorted linked lists
45 Node* head1 = new Node(1);
46 head1->next = new Node(3);
47 head1->next->next = new Node(5);
48
49 Node* head2 = new Node(2);
50 head2->next = new Node(4);
51 head2->next->next = new Node(6);
52
53 // Merge the two lists
54 Node* mergedHead = mergeLinkedLists(head1, head2);
55
56 // Print the merged list
57 while (mergedHead) {
58 cout << mergedHead->data << " ";
59 mergedHead = mergedHead->next;
60 }
61
62 return 0;
63}xxxxxxxxxx63
}using namespace std;// Linked List Nodestruct Node { int data; Node* next; Node(int d) : data(d), next(nullptr) {}};// Function to merge two sorted linked listsNode* mergeLinkedLists(Node* head1, Node* head2) { // Create a dummy node to store the merged list Node* dummy = new Node(0); Node* tail = dummy; // Merge the two lists while (head1 && head2) { if (head1->data <= head2->data) { tail->next = head1; head1 = head1->next; } else { tail->next = head2; head2 = head2->next; } tail = tail->next; } // Append any remaining nodes of the first listOUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment