Merging Two Sorted Linked Lists Using Iterative Method in Python

Problem Explanation

You are given two sorted linked lists list1 and list2.
Your task is to merge them into a single sorted linked list.

The new list should be created by reusing the existing nodes.

Example:

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

• Output: [1,1,2,3,4,4]

• Input: list1 = [], list2 = []

• Output: []

---

Method Used: Iterative Approach (Two Pointer Technique)

Idea

• Compare nodes from both lists
• Pick the smaller one
• Move forward
• Repeat until one list ends

---

Why This Method?

• Time complexity: O(n + m)
• Space complexity: O(1)
• Efficient and easy to implement
• No extra memory required

---

Python Code with Explanation

class Solution:
    def mergeTwoLists(self, list1, list2):

Defines the function.

---

        dummy = ListNode(0)

Create a dummy node to simplify merging.

---

        tail = dummy

tail will build the merged list.

---

        while list1 and list2:

Loop until one list becomes empty.

---

            if list1.val < list2.val:

Compare values of both lists.

---

                tail.next = list1
                list1 = list1.next

Attach smaller node from list1.

---

            else:
                tail.next = list2
                list2 = list2.next

Attach smaller node from list2.

---

            tail = tail.next

Move tail forward.

---

        if list1:
            tail.next = list1

Attach remaining nodes from list1.

---

        if list2:
            tail.next = list2

Attach remaining nodes from list2.

---

        return dummy.next

Return the merged list (skip dummy node).

---

Complete Code

class Solution:
    def mergeTwoLists(self, 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

        if list1:
            tail.next = list1
        if list2:
            tail.next = list2

        return dummy.next

---

Step-by-Step Example

Input:

1 → 2 → 4  
1 → 3 → 4

Steps:

• Compare and merge nodes
• Maintain sorted order

Output:

1 → 1 → 2 → 3 → 4 → 4

---

Key Takeaway

Using a dummy node simplifies merging logic and helps efficiently combine two sorted linked lists in one pass.

---