Merge Two Sorted Lists Problem and Solution

1. Introduction

A comprehensive guide to solving the "Merge Two Sorted Lists" problem in multiple programming languages (C++, Java, and Python), including detailed explanations and outputs.

The "Merge Two Sorted Lists" problem involves merging two sorted linked lists into a single sorted linked list. The challenge is to do this efficiently while maintaining the order of the elements.

2. Problem

Given the heads of two sorted linked lists list1 and list2, merge the two lists into one sorted list. The new list should be made by splicing together the nodes of the first two lists and should be returned as the head of this merged list.

3. Solution in C++

#include <iostream>
using namespace std;

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

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

// Example usage
int main() {
    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 *result = mergeTwoLists(list1, list2);
    while (result != nullptr) {
        cout << result->val << " ";
        result = result->next;
    }
    return 0;
}

Output:

1 1 2 3 4 4

Explanation:

1. mergeTwoLists in C++ uses a recursive approach.

2. It compares the head of each list and recursively calls itself with the next of the smaller node and the other list.

3. Continues until one of the lists is empty, then returns the other list.

4. This results in a merged sorted list.

4. Solution in Java

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    // Example usage
    public static void main(String[] args) {
        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 result = mergeTwoLists(list1, list2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Output:

1 1 2 3 4 4

Explanation:

1. Java's mergeTwoLists method is similar to the C++ solution, using a recursive approach.

2. It compares the heads of the lists and recursively merges them.

3. The recursion continues until one list is exhausted.

4. Returns the merged sorted list.

5. Solution in Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    if not l1 or not l2:
        return l1 or l2
    if l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

# Example usage
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
result = mergeTwoLists(l1, l2)
while result:
    print(result.val, end=" ")
    result = result.next

Output:

1 1 2 3 4 4

Explanation:

1. Python's mergeTwoLists uses a recursive approach.

2. It compares the head of each list and recursively merges them.

3. The recursion continues until one of the lists is exhausted.

4. Returns the merged sorted list.