Merge Two Sorted Lists Problem Statement in Java, Python, JavaScript and TestScript

🧩 Merge Two Sorted Lists Problem Statement in Java, Python, JavaScript and TestScript Interview

Merge Two Sorted Lists

You are 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.

Merge Two Sorted Lists

Return the head of the merged linked list.

📥 Input

```
list1 = [1,2,4]
```
,
```
list2 = [1,3,4]
```

📤 Output

```
[1,1,2,3,4,4]
```

🔁 Example 2

Input:

list1 = []

list2 = []

Output:

[]

🔁 Example 3

Input:

list1 = []

list2 = [0]

Output:

[0]

📌 Constraints

The number of nodes in both lists is in the range
```
[0, 50]
```
```
-100 <= Node.val <= 100
```
Both
```
list1
```
and
```
list2
```
are sorted in non-decreasing order.

🐍 Python Solution

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

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        sentinel = ListNode()
        current = sentinel

        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next

        current.next = list1 if list1 else list2
        return sentinel.next

🔍 Explanation:

ListNode class defines a node in a singly linked list.
sentinel is a dummy node used to simplify list merging.
current points to the last node in the merged list.
It iterates through both lists, appending the smaller node to the result.
Remaining nodes (if any) are appended after the loop.

☕ Java Solution

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode current = dummyHead;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }

        current.next = (list1 == null) ? list2 : list1;
        return dummyHead.next;
    }
}

🔍 Explanation:

dummyHead helps track the head of the merged list.
current is updated as nodes are merged.
After merging, leftover nodes are added directly.

📜 JavaScript Solution

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummyHead = new ListNode();
        ListNode* current = dummyHead;

        while (list1 && list2) {
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }

        current->next = list1 ? list1 : list2;
        return dummyHead->next;
    }
};

🔍 Explanation:

This is C++-style syntax but often used in system-level JavaScript implementations like WebAssembly or TypeScript compilers.
Follows the same logic: merge by comparing current node values.

🔷 TypeScript Solution

interface ListNode {
    val: number;
    next: ListNode | null;
}

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    if (list1 === null || list2 === null) {
        return list1 || list2;
    }

    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

🔍 Explanation:

This is a recursive approach in TypeScript.
If either list is null, return the other.
Compare head values and recursively build the merged list.

❓ Frequently Asked Questions (FAQs)

Q1: What is the time complexity of the merge operation?

A: O(n + m), where n and m are the lengths of the two lists. Each node is visited once.

Q2: Can we merge lists without using extra space?

A: Yes, all the implementations use constant extra space (O(1)), not counting the output list.

Q3: What happens if one list is empty?

A: The non-empty list is returned as is.

Q4: Which implementation is most readable for beginners?

A: Python or TypeScript recursive version is simplest to understand.

Q5: Why do we use a dummy or sentinel node?

A: It simplifies edge cases like inserting at the head and allows consistent handling of all nodes.

Merge Two Sorted Lists Problem Statement in Java, Python, JavaScript and TestScript