Merge Two Sorted Linked Lists

This is one of the most frequently asked Linked List interview questions because it tests whether you can manipulate pointers without creating unnecessary extra space.

The core idea is exactly the same as the Merge Step of Merge Sort.

If you understand this problem well, you'll find Merge Sort on Linked Lists much easier later.

---

Problem Statement

You are given the heads of two sorted linked lists.

Merge the two lists into one sorted linked list and return its head.

Example

Input:

List1: 1 -> 2 -> 4
List2: 1 -> 3 -> 4

Output:

1 -> 1 -> 2 -> 3 -> 4 -> 4

---

Brute Force Approach

Intuition

A straightforward approach is:

1. Traverse both linked lists.
2. Store all values inside an ArrayList.
3. Sort the ArrayList.
4. Create a new linked list from the sorted values.

Although easy to think about, we're using extra space and ignoring the fact that both lists are already sorted.

Complexity

Time Complexity  : O((N + M) log(N + M))
Space Complexity : O(N + M)

where:

N = length of list1
M = length of list2

---

Moving Towards the Optimal Approach

Notice something important:

Both linked lists are already sorted.

So instead of collecting all elements and sorting again, we can compare the current nodes of both lists and always pick the smaller one.

This is exactly how the merge step in Merge Sort works.

---

Optimal Approach - Two Pointer Technique

Maintain:

cur1
cur2

for traversing both lists.

Also maintain:

dummy
tail

to build the merged list.

At every step:

• Compare current nodes.
• Attach the smaller node.
• Move the corresponding pointer forward.
• Move tail forward.

When one list finishes, simply attach the remaining nodes of the other list.

---

Visual Intuition

Initial State

List1: 1 -> 2 -> 4

List2: 1 -> 3 -> 4

Dummy node:

-1
 ^
tail

---

Step 1

Compare:

1 and 1

Take any one (say from List1)

-1 -> 1

---

Step 2

Compare:

2 and 1

Take:

1

Result:

-1 -> 1 -> 1

---

Step 3

Compare:

2 and 3

Take:

2

Result:

-1 -> 1 -> 1 -> 2

---

Continue similarly.

Final List:

1 -> 1 -> 2 -> 3 -> 4 -> 4

---

Dry Run

Input

List1 = 1 -> 2 -> 4

List2 = 1 -> 3 -> 4

Iteration 1

1 <= 1

Take List1 node

Merged:
1

Iteration 2

2 > 1

Take List2 node

Merged:
1 -> 1

Iteration 3

2 < 3

Take List1 node

Merged:
1 -> 1 -> 2

Iteration 4

4 > 3

Take List2 node

Merged:
1 -> 1 -> 2 -> 3

Iteration 5

4 <= 4

Take List1 node

Merged:
1 -> 1 -> 2 -> 3 -> 4

List1 finishes.

Attach remaining List2:

4

Final:

1 -> 1 -> 2 -> 3 -> 4 -> 4

---

Optimal Java Solution

class Solution {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode cur1 = list1;
        ListNode cur2 = list2;

        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;

        while (cur1 != null && cur2 != null) {

            if (cur1.val <= cur2.val) {

                tail.next = cur1;
                cur1 = cur1.next;

            } else {

                tail.next = cur2;
                cur2 = cur2.next;
            }

            tail = tail.next;
        }

        while (cur1 != null) {

            tail.next = cur1;
            cur1 = cur1.next;
            tail = tail.next;
        }

        while (cur2 != null) {

            tail.next = cur2;
            cur2 = cur2.next;
            tail = tail.next;
        }

        return dummy.next;
    }
}

---

Why Dummy Node?

Without a dummy node, we'd need special handling for the first node of the merged list.

Using:

ListNode dummy = new ListNode(-1);

allows us to treat every insertion exactly the same.

At the end:

return dummy.next;

gives us the actual head.

---

Complexity Analysis

Time Complexity  : O(N + M)

Space Complexity : O(1)

• Each node is visited exactly once.
• No extra data structure is used.
• Existing nodes are reused.

---

Key Takeaway

Whenever you hear:

• Merge Two Sorted Lists
• Merge K Sorted Lists
• Merge Sort on Linked List

Immediately think:

"Always compare the current elements and take the smaller one."

This simple pattern is the foundation of many sorting and linked list interview questions.

---