1. Understanding the Problem

You are given the heads of two sorted linked lists, list1 and list2. Your task is to merge the two lists into one single, sorted linked list and return the head of this newly merged list.

The Rules of the Merge:

• The final list should be made by splicing together the exact nodes of the first two lists (do not create new nodes).
• The input lists are already sorted in non-decreasing order.
• If one of the lists is empty, the merged list is simply the other list.

A Quick Example

Imagine list1 = [1 -> 2 -> 4] and list2 = [1 -> 3 -> 4].

You want to combine them in order. You compare the first elements, pick the smallest, and move forward. The final result should look like this: [1 -> 1 -> 2 -> 3 -> 4 -> 4].

2. The Core Intuition: The Zipper Technique

Think of this problem like zipping up a jacket. The teeth on the left side are list1, and the teeth on the right side are list2. You look at the next available tooth on both sides, grab the smaller one, and pull the zipper up. You repeat this until one side runs out of teeth, at which point you just pull the rest of the remaining side up.

To implement this in code without losing our place, we use a classic linked list trick: the Dummy Node. A dummy node gives us a starting point to attach our merged nodes to, saving us from writing messy edge-case logic for an empty starting list.

3. The Logic Step-by-Step

Here is the exact algorithm to successfully merge the lists:

1. Create a dummy node. This acts as the anchor for our new list.
2. Create a current pointer and point it to the dummy node. We will use this to build the new list node by node.
3. While both list1 and list2 are not empty:
   • Compare the values of the nodes at the heads of list1 and list2.
   • If list1.val is smaller or equal, point current.next to list1, and move the list1 pointer forward.
   • Otherwise, point current.next to list2, and move the list2 pointer forward.
   • Move our current pointer forward to the node we just added.
4. When one list is exhausted: Simply point current.next to the remaining nodes of the other list. They are already sorted!
5. Return dummy.next, which is the true head of our merged list.

4. Complexity Analysis

• Time Complexity: O(N + M) — Where N is the length of list1 and M is the length of list2. We iterate through each node exactly once.
• Space Complexity: O(1) — We are only rearranging existing pointers. We do not allocate any new data structures or arrays, making this extremely memory efficient.

5. Code Implementations

Expand the sections below to see the optimal O(1) space implementation in your preferred programming language.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1, list2):
        # Create a dummy node to act as the start of the merged list
        dummy = ListNode()
        current = dummy
        
        # Traverse both lists while neither is empty
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            # Move the current pointer forward
            current = current.next
            
        # Attach the remaining elements of the list that is not empty
        if list1:
            current.next = list1
        elif list2:
            current.next = list2
            
        # Return the actual head of the merged list
        return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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;
        }
        
        // At least one of the lists is null now, attach the other
        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }
        
        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* current = &dummy;
        
        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;
        }
        
        if (list1 != nullptr) {
            current->next = list1;
        } else {
            current->next = list2;
        }
        
        return dummy.next;
    }
};

6. Conclusion: You Are Ready

By understanding how to merge two sorted lists, you have just mastered the foundational skill for many advanced linked list problems (like sorting a linked list or merging K sorted lists). The "Dummy Node" pattern you learned here will save you from countless null pointer exceptions and messy edge cases in the future. Keep reviewing the logic, trace the pointers on paper, and your confidence will only continue to grow!