Merging Two Sorted Linked Lists in Python

🚀 Problem Statement

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

Your task is to:

• Merge them into a single sorted linked list
• Do this by reusing the existing nodes (not creating new ones)
• Return the head of the merged list

---

💡 Example

Input:
list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4

Output:
1 -> 1 -> 2 -> 3 -> 4 -> 4

---

🧠 Intuition

Since both lists are already sorted:

• Compare the first nodes of each list
• Pick the smaller one and move forward
• Repeat until one list is exhausted
• Attach the remaining part of the other list

---

🛠️ Approach (Iterative)

We use a dummy node to simplify handling the head of the merged list.

Steps:

1. Create a dummy node
2. Use a pointer (current) to build the result
3. Compare nodes from both lists
4. Attach the smaller node to current
5. Move pointers forward
6. Attach any remaining nodes

---

🧾 Python Implementation

# 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):
        dummy = ListNode()
        current = dummy

        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

        # Attach remaining nodes
        if list1:
            current.next = list1
        else:
            current.next = list2

        return dummy.next

---

⏱️ Complexity Analysis

• Time Complexity: O(n + m)
  (We traverse both lists once)

• Space Complexity: O(1)
  (No extra space used; in-place merge)

---

🔁 Alternative: Recursive Approach

You can also solve this problem recursively:

class Solution:
    def mergeTwoLists(self, list1, list2):
        if not list1:
            return list2
        if not list2:
            return list1

        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

---

📌 Key Takeaways

• Use a dummy node to simplify linked list operations
• Think in terms of pointer manipulation
• Practice both iterative and recursive solutions

• This problem is a foundation for more complex ones like:

  • Merge K sorted lists
  • Linked list sorting

---

🎯 Final Thoughts

This problem is simple but powerful. Mastering it builds confidence in handling linked lists—one of the trickiest topics for beginners.