DEV Community

Cover image for Merge Two Linked List
Abirami Prabhakar
Abirami Prabhakar

Posted on

Merge Two Linked List

lets first understand the question

Given two sorted linked lists list1 and list2, merge them into one sorted linked list and return the head of the merged list

sample i/p and o/p from a question

Input:

list1 = [1,2,4]  
list2 = [1,3,4]  

Enter fullscreen mode Exit fullscreen mode

Output:

[1,1,2,3,4,4]  
Enter fullscreen mode Exit fullscreen mode

Explanation: both lists are already sorted, so we merge them in such a way that the final list is also sorted

how to approach the solution
I started with a question "How do I compare two linked lists element by element?"

since the lists are already sorted, we don’t need to sort again

so the idea is simple → compare elements and take the smaller one

how it works

let the given lists be

list1 = 1 → 2 → 4  
list2 = 1 → 3 → 4 
Enter fullscreen mode Exit fullscreen mode

we compare both nodes step by step

1 vs 1 → take 1  
2 vs 1 → take 1  
2 vs 3 → take 2  
4 vs 3 → take 3  
4 vs 4 → take 4  
remaining → 4 
Enter fullscreen mode Exit fullscreen mode

so the final list becomes

1 → 1 → 2 → 3 → 4 → 4  
Enter fullscreen mode Exit fullscreen mode
Approach
Enter fullscreen mode Exit fullscreen mode

we use a dummy node to make linking easy
current pointer is used to build the new list
compare both lists
attach smaller node
move that list forward
at the end, attach remaining elements

Algorithm

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


def mergeTwoLists(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
Enter fullscreen mode Exit fullscreen mode

Top comments (0)