---

1. Problem Summary

You are given the heads of two singly linked lists, list1 and list2.

Both linked lists are:

• sorted in non-decreasing order
• may be of different lengths
• may contain duplicates

Your task is to merge the two lists into a single sorted linked list and return the head of the merged list.

Important details:

• The merged result must reuse the existing nodes
• You should not create new list nodes for values
• The final list must maintain sorted order

Example interpretation:
If the lists are:

list1: 1 → 2 → 4
list2: 1 → 3 → 4

Merged result becomes:

1 → 1 → 2 → 3 → 4 → 4

---

2. Key Insights

Comparison drives merging

At each step, compare the current nodes of both lists and append the smaller one.

A dummy head simplifies pointer management

Creating a fake starting node avoids edge-case handling for first insertion.

No need to traverse both lists fully

Once one list is exhausted, the remainder of the other list can be appended directly.

Sorted order preserved naturally

Because input lists are sorted, merging by comparison guarantees sorted output.

---

3. Approach

Iterative merge using pointer navigation

Steps:

1. Create a dummy node to act as starting reference.
2. Maintain a current pointer to build the merged list.
3. While both lists have nodes:
   • compare list1.val and list2.val
   • attach the smaller node to current.next
   • advance the pointer on the chosen list
   • advance current
4. After loop ends:
   • append remaining nodes from the non-exhausted list
5. Return dummy.next as merged head.

This produces an ordered list in-place.

---

4. Time and Space Complexity

Time Complexity: O(N + M)

Where:

• N = length of list1
• M = length of list2

All nodes are visited once.

Space Complexity: O(1)

No new nodes created, only pointer manipulations.

---

5. Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

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

        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;
        }

        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }

        return dummy.next;
    }
}

---

6. Dry Run Examples

Example 1

Input:

list1 = 1 → 2 → 4
list2 = 1 → 3 → 4

Process sequence:
1 ≤ 1 → attach list1 node
current = 1
then attach 1 from list2
then 2
then 3
then 4
then remaining 4

Output:

1 → 1 → 2 → 3 → 4 → 4

---

Example 2

Input:

list1 = []
list2 = 0 → 2 → 5

list1 empty → append list2 entirely

Output:

0 → 2 → 5

---

Example 3

Input:

list1 = 1 → 1 → 1
list2 = 1 → 1

Repeated values allowed
Ordering consistent

Output:

1 → 1 → 1 → 1 → 1

---

Example 4

Input:

list1 = 5 → 7 → 9
list2 = 1 → 2 → 3

All list2 values smaller until exhausted

Output:

1 → 2 → 3 → 5 → 7 → 9

---

Example 5

Input:

list1 = 2
list2 = 2

Comparison allows equal values to attach in order

Output:

2 → 2

---

7. Why This Solution Works

• Uses sorted nature of lists to merge efficiently
• Avoids extra memory allocation
• Dummy node simplifies linking logic
• Guarantees sorted output without rearranging values
• Handles empty list cases seamlessly

---

8. Common Mistakes

1. Creating new nodes unnecessarily instead of reusing existing ones
2. Forgetting to link remaining nodes after loop
3. Mishandling equal values (they must be allowed)
4. Attempting recursive merge without considering stack depth
5. Modifying input pointers incorrectly leading to cycles