CA 15 - Merge Two Linked List

🔗 Merge Two Sorted Lists – Python (Efficient Merging)

Hi All,

Today I solved an important problem: Merging two sorted linked lists into a single sorted linked list.

---

📌 Problem Statement

Given the heads of two sorted linked lists, list1 and list2, merge them into a single sorted linked list.

The merged list should reuse the existing nodes of the two input lists.

---

🔍 Example

Input:

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

Output:

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

---

Edge Cases:

1. Both lists empty → []
2. One list empty → [0]

---

💡 Why Merge Two Sorted Lists?

👉 This problem is a classic coding interview question because:

• It teaches pointer manipulation in linked lists
• Efficiently merges without creating extra nodes
• Forms the basis for Merge Sort on linked lists

---

💡 Approach

🔹 Two-Pointer Method

1. Create a dummy node to simplify edge cases
2. Use pointers to traverse list1 and list2
3. Compare current nodes → attach the smaller to the merged list
4. Move the pointer forward
5. Repeat until one list ends
6. Attach remaining nodes of the non-empty list

---

🧠 Step-by-Step Logic

Step 1: Initialize

• Create dummy node and tail pointer

Step 2: Traverse Both Lists

• Compare nodes:
  • list1.val < list2.val → attach list1
  • else → attach list2

Step 3: Attach Remaining Nodes

• When one list is exhausted, attach the other

Step 4: Return Merged List

• Return dummy.next as the head of the merged list

---

💻 Python Code

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

def mergeTwoLists(list1, list2):
    dummy = ListNode(0)
    tail = dummy

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

    # Attach remaining nodes
    tail.next = list1 if list1 else list2

    return dummy.next

---

🔍 Dry Run

For:

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

Steps:

• Compare 1 & 1 → attach 1
• Compare 2 & 1 → attach 1
• Compare 2 & 3 → attach 2
• Compare 4 & 3 → attach 3
• Compare 4 & 4 → attach 4
• Attach remaining 4 → [1,1,2,3,4,4]

---

🖥️ Sample Output

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

---

⚡ Complexity Analysis

• Time Complexity: O(n + m) ✅
• Space Complexity: O(1) (in-place merging, no extra nodes)

---

🧠 Why this is important?

• Builds strong pointer manipulation skills
• Forms the core of Merge Sort on linked lists
• Frequently asked in coding interviews

---

✅ Conclusion

This problem helps understand:

• Efficient merging of linked lists
• Dummy node technique for cleaner code
• Traversing multiple lists simultaneously

🚀 Must-know for coding interviews and linked list manipulation!

---