Merging Two Linked Lists

In this task, I worked on merging two sorted linked lists into a single sorted linked list. This problem helped me understand how linked lists work and how to handle pointers.

What I Did

I created a function mergeTwoLists that takes two sorted linked lists as input and merges them into one sorted list.

For example:
List1: 1 → 3 → 5
List2: 2 → 4 → 6
Output: 1 → 2 → 3 → 4 → 5 → 6

How I Solved It

To solve this, I used a dummy node to make the process easier. This dummy node helps in building the new list without worrying about the head.

I used a pointer called current to keep track of the last node in the merged list.

Then I compared the nodes of both lists:

• If the value in list1 is smaller, I added that node to the new list and moved list1 forward
• Otherwise, I added the node from list2 and moved list2 forward

I repeated this until one of the lists became empty.

After that:

• If any elements were left in either list, I simply attached them to the end

Code

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

class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(-1)
        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

How It Works

The function builds a new linked list by always choosing the smaller node from the two lists. Since both lists are already sorted, this ensures the final list is also sorted.

The dummy node helps simplify the process, and in the end, we return the merged list starting from dummy.next.