🔗 Merge Two Sorted Linked Lists (Step-by-Step Guide)

Merging two sorted linked lists is a fundamental problem in data structures.
It helps you understand linked list traversal, pointers, and merging logic.

---

📌 Problem Statement

You are given two sorted linked lists list1 and list2.

Merge them into a single sorted linked list and return its head.

The new list should be created by reusing the existing nodes (no extra list).

---

🔍 Examples

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

Example 2:
Input: list1 = [], list2 = []
Output: []

Example 3:
Input: list1 = [], list2 = [0]
Output: [0]

---

🧠 Intuition

Since both lists are already sorted:

👉 Compare elements from both lists
👉 Pick the smaller one
👉 Move forward

This is similar to the merge step in merge sort

---

🔄 Approach (Iterative Method)

Step-by-Step:

1. Create a dummy node to store result
2. Use a pointer current to build the list
3. Compare nodes of both lists:

• Attach smaller node to result
• Move that list forward
  1. When one list ends, attach the remaining nodes of the other list

---

💻 Python Code

```python id="m1"
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

def mergeTwoLists(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

---

🧾 Dry Run

For:
list1 = [1 → 2 → 4]
list2 = [1 → 3 → 4]

Steps:

* Compare 1 and 1 → pick 1
* Compare 2 and 1 → pick 1
* Compare 2 and 3 → pick 2
* Compare 4 and 3 → pick 3
* Compare 4 and 4 → pick 4
* Attach remaining 4

Final: [1 → 1 → 2 → 3 → 4 → 4]

---

⚡ Complexity

Time Complexity: O(n + m)
Space Complexity: O(1)

---

🔥 Why This Works

* Uses existing nodes (no extra memory)
* Efficient traversal of both lists
* Maintains sorted order

---

⚠️ Edge Cases

* One list is empty
* Both lists are empty
* Lists of different sizes

---

🏁 Conclusion

Merging two sorted linked lists is an important concept that teaches:

* Pointer manipulation
* Efficient traversal
* Real-world merging logic

Mastering this helps in many advanced problems like merge sort and linked list operations.