Problem Statement

Given two sorted linked lists, list1 and list2, merge them into a single sorted linked list. The merged linked list should be made by splicing together the nodes of the two given lists.

Examples:

Example 1:

Input: list1 = 1 -> 2 -> 4, list2 = 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Example 2:

Input: list1 = 1 -> 3 -> 5, list2 = 2 -> 4 -> 6
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Example 3:

Input: list1 = 5 -> 10 -> 15, list2 = 3 -> 8 -> 9 -> 17
Output: 3 -> 5 -> 8 -> 9 -> 10 -> 15 -> 17

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Extract all elements from both linked lists into an additional array, sort the array, and then create a new combined linked list from the sorted elements.

Approach:

1. Initialize an empty array and iterate through each node of both the first and second linked lists, adding their elements to the array. This ensures that all elements from both lists are collected in one place for easy sorting.
2. Sort the array in ascending order using a sorting algorithm such as quick sort, merge sort, or an inbuilt library function. Sorting the array ensures that the combined elements from both lists are in the correct order for merging.
3. Create a new linked list from the sorted array. Initialize a dummy node to act as the head of the merged linked list. Iterate through the sorted array, creating a new linked list node for each element, and link these nodes together. Finally, return the next node of the dummy node as the head of the merged sorted linked list.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int data1) {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1) {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    // Function to merge two sorted linked lists
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        vector<int> arr;
        ListNode* temp1 = list1;
        ListNode* temp2 = list2;

        
        // Add elements from list1 to the vector
        while(temp1 != NULL){
            arr.push_back(temp1->val); 
            // Move to the next node in list1
            temp1 = temp1->next; 
        }

        // Add elements from list2 to the vector
        while(temp2 != NULL){
            arr.push_back(temp2->val);
            // Move to the next node in list2
            temp2 = temp2->next; 
        }

        // Sorting the vector in ascending order
        sort(arr.begin(), arr.end());

        // Sorted vector to linked list
        ListNode* dummyNode = new ListNode(-1);
        ListNode* temp = dummyNode;
        for(int i = 0; i < arr.size(); i++){
            temp->next = new ListNode(arr[i]); 
            temp = temp->next; 
        }

        // Return the head of 
        // merged sorted linked list
        return dummyNode->next; 
    }
};

// Function to print the linked list
void printLinkedList(ListNode* head) {
    ListNode* temp = head;
    while (temp != nullptr) {
        // Print the data of the current node
        cout << temp->val << " "; 
        // Move to the next node
        temp = temp->next; 
    }
    cout << endl;
}

int main() {
    // Example Linked Lists
    ListNode* list1 = new ListNode(1);
    list1->next = new ListNode(3);
    list1->next->next = new ListNode(5);

    ListNode* list2 = new ListNode(2);
    list2->next = new ListNode(4);
    list2->next->next = new ListNode(6);

    cout << "First sorted linked list: ";
    printLinkedList(list1);

    cout << "Second sorted linked list: ";
    printLinkedList(list2);

    Solution solution;
    ListNode* mergedList = solution.mergeTwoLists(list1, list2);

    cout << "Merged sorted linked list: ";
    printLinkedList(mergedList);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N1 + N2) + O(N log N) + O(N) where N1 is the number of linked list nodes in the first list, N2 is the number of linked list nodes in the second list, and N is the total number of nodes (N1 + N2). Traversing both lists into the array takes O(N1 + N2), sorting the array takes O((N1 + N2) X log(N1 + N2)), and then traversing the sorted array and creating a list gives us another O(N1 + N2).
• Space Complexity: O(N) + O(N) where N is the total number of nodes from both lists (N1 + N2). O(N) to store all the nodes of both the lists in an external array and another O(N) to create a new combined list.

2️⃣ Optimal Approach:

Intuition:

To merge two sorted linked lists into a single sorted linked list, we can utilize a two-pointer approach.

A more efficient approach involves merging the given sorted linked lists directly without the need for an intermediate array. By taking advantage of the fact that the linked lists are already sorted, we can use a simple comparison strategy.
Position a pointer each at the beginning of both lists. Compare the current values at these pointers and choose the smaller value to add to the new merged list. Move the pointer forward in the list from which the smaller value was taken. Repeat this process until one of the lists is fully merged. At this point, attach the remaining nodes of the other list to the merged list, as they are already in order.

Here's the step-by-step intuition:

1. Starting Point:
   • Begin with two pointers, one for each linked list (list1 and list2).
   • We need a dummy node to act as the head of the new merged linked list, simplifying the edge cases where the merged list starts with either list1 or list2.
2. Comparison and Merge:
   • Compare the current nodes pointed to by the two pointers.
   • Append the smaller node to the merged linked list.
   • Move the pointer forward on the list from which the smaller node was selected.
3. Continue Until One List is Exhausted:
   • Continue the process until one of the linked lists is fully traversed.
4. Attach the Remaining Nodes:
   • Once one of the lists is fully traversed, append the remaining nodes from the other list to the merged linked list.
5. Result:
   • The merged linked list is built in sorted order because we always choose the smallest available node from the two lists.

Approach:

1. Set up two pointers at the start of each input linked list. Create a dummy node to serve as the anchor for the beginning of the merged list and use a separate traversal pointer to build the combined list.
2. While both lists have remaining nodes, compare their current values. Attach the smaller value to the merged list and advance the traversal pointer, along with the pointer from the list from which the smaller value was taken.
3. When one of the lists is fully traversed, directly attach the remaining nodes from the other list to the merged list, as they are already in sorted order.
4. The merged list starts after the dummy node. Return the next node of the dummy node as the head of the newly merged and sorted linked list.

Code:

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    // Create a dummy node to simplify edge cases.
    ListNode dummy(0);
    ListNode* current = &dummy;

    // Traverse both lists
    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val <= list2->val) {
            current->next = list1;
            list1 = list1->next;
        } else {
            current->next = list2;
            list2 = list2->next;
        }
        current = current->next;
    }

    // Append the remaining nodes of list1 or list2, if any.
    if (list1 != nullptr) {
        current->next = list1;
    } else {
        current->next = list2;
    }

    // The merged linked list starts from the next node of dummy.
    return dummy.next;
}

// Utility function to print the linked list
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    // Example Usage
    ListNode* list1 = new ListNode(1);
    list1->next = new ListNode(2);
    list1->next->next = new ListNode(4);

    ListNode* list2 = new ListNode(1);
    list2->next = new ListNode(3);
    list2->next->next = new ListNode(4);

    ListNode* mergedList = mergeTwoLists(list1, list2);

    printList(mergedList); // Output: 1 1 2 3 4 4

    return 0;
}

Complexity Analysis

• Time Complexity:
  • O(m + n): We traverse each node of both linked lists exactly once. Here, m and n are the lengths of list1 and list2, respectively.
• Space Complexity:
  • O(1): The algorithm uses a constant amount of extra space. The new nodes are reused and directly linked to form the merged list, so no additional linked list data structures are created.