Lecture 141:- Merge Two Sorted Lists

To merge two sorted singly linked lists into a single sorted linked list, you can use a simple iterative approach. Here's how you can do it:

1. Create a new dummy node to serve as the head of the merged list.
2. Initialize two pointers, current and temp, pointing to the dummy node.
3. Compare the values of the nodes from the two input lists. Attach the smaller node to the temp pointer, and move the corresponding list's pointer forward.
4. Repeat the comparison and attaching process until you reach the end of one of the lists.
5. Attach the remaining nodes from the non-empty list to the temp pointer.
6. The merged list is now connected through the dummy.next pointer.

Here's a C++ implementation of this approach:

cppCopy code

#include <iostream> class Node { public: int data; Node* next; Node(int value) : data(value), next(nullptr) {} }; Node* mergeSortedLists(Node* list1, Node* list2) { Node dummy(0); // Dummy node to serve as the head of the merged list Node* temp = &dummy; // Pointer to the current position in the merged list while (list1 && list2) { if (list1->data < list2->data) { temp->next = list1; list1 = list1->next; } else { temp->next = list2; list2 = list2->next; } temp = temp->next; } // Attach remaining nodes from the non-empty list if (list1) { temp->next = list1; } if (list2) { temp->next = list2; } return dummy.next; // Merged list starts from dummy.next } void displayList(Node* head) { while (head) { std::cout << head->data << " "; head = head->next; } std::cout << std::endl; } int main() { Node* list1 = new Node(1); list1->next = new Node(3); list1->next->next = new Node(5); Node* list2 = new Node(2); list2->next = new Node(4); list2->next->next = new Node(6); std::cout << "List 1: "; displayList(list1); std::cout << "List 2: "; displayList(list2); Node* mergedList = mergeSortedLists(list1, list2); std::cout << "Merged List: "; displayList(mergedList); return 0; }

In this example, two sorted linked lists (list1 and list2) are merged using the mergeSortedLists function. The merged list is displayed using the displayList function.

The time complexity of this approach is O(N + M), where N and M are the lengths of the input lists, as each node is visited exactly once.