CA 15 - Merge Two Linked List

Problem

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

The task is to merge both lists into one sorted linked list by splicing together their nodes.

Return the head of the merged linked list.

Output

Example 1
Output: [1, 1, 2, 3, 4, 4]
Example 2
Output: []
Example 3
Output: [0]

My Approach

To solve this problem, I used an iterative method with a dummy node.

I create a dummy node to simplify handling the head of the merged list.

Then I use a pointer to build the new list step by step.

I compare the current nodes of both lists:

If the value in list1 is smaller, I attach it to the merged list and move list1 forward
Otherwise, I attach the node from list2 and move list2 forward

I continue this until one of the lists becomes empty.

Finally, I attach the remaining nodes from the non-empty list.

This works because both lists are already sorted, so we can merge them efficiently by comparing elements one by one.

This approach is efficient because:

It requires only one traversal
It uses constant extra space
Code

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(0)
        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
        if list1:
            current.next = list1
        else:
            current.next = list2
        return dummy.next