Merge Two Sorted Lists | LeetCode 21 | Python | Solution

Click here to see the problem details.

Problem Overview

The problem description is pretty straightforward. We are given two sorted Linked List. And we have to merge those given Lists into one sorted list. That’s the problem.

Suppose our given two lists are 1 -> 3 and 2 -> 4. And the result will be 1 -> 2 -> 3 -> 4.

We can achieve this solution using the merge sort algorithmic way. So let’s get into the code.

Coding Part

Our given lists are sorted. So this makes our task easier.

First, we create a dummy head node to store all sorted nodes. Then a variable for tracking the sorted list. After that, we will run a loop until one of the given lists reaches the end. Inside the loop, we will check the current node of both lists. From there, we will add the one that will fulfill our condition to the final sorted list. And then will move one step ahead.

After the loop, there is a chance that one of the given lists will not be completely added to the final list. So, we will add the rest of the list to the final sorted list by checking.

And finally, we will return the head.next since the head node itself is not part of the sorted list. But the rest of the list is part of the sorted list.

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode()
        current = head
        
        while l1 != None and l2 != None:
            if l1.val <= l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            
            current = current.next
            
        if l1 != None:
            current.next = l1
        
        if l2 != None:
            current.next = l2
        
        return head.next

Final Words

This answer will be accepted. Before submitting an answer, try to understand the whole thing. And try to go through the code with a simple test case for better understanding. It helps a lot.