Merge two sorted list

Merging Two Sorted Linked Lists

1.Merging two sorted linked lists is a fundamental problem in data structures. It is commonly used in algorithms like merge sort and appears frequently in coding interviews.

2.The goal is simple: given two sorted linked lists, combine them into one sorted linked list.
**
Understanding the Problem**

Suppose we have two sorted linked lists:

list1: 1 -> 3 -> 5
list2: 2 -> 4 -> 6

After merging, the result should be:
1 -> 2 -> 3 -> 4 -> 5 -> 6

The final list must remain sorted.

Approach Used

We use an iterative approach with a dummy node to simplify pointer handling.

The idea is:

1. Compare nodes from both lists
2. Attach the smaller node to the result
3. Move forward in that list
4. Continue until one list is exhausted
5. Attach the remaining nodes

Code
class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = tail = ListNode()
        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
        tail.next = list1 or list2
        return dummy.next

Step-by-Step Explanation

1. Create Dummy Node

dummy = tail = ListNode()

dummy is a placeholder node that helps simplify the logic
tail keeps track of the last node in the merged list

2. Traverse Both Lists

while list1 and list2:
We continue looping as long as both lists have nodes.

3. Compare Nodes

if list1.val <= list2.val:
Compare the current values of both lists
Choose the smaller value

4. Attach Node to Result
tail.next, list1 = list1, list1.next

or

tail.next, list2 = list2, list2.next
Attach the selected node to the merged list
Move forward in the corresponding list

5. Move Tail Pointer

tail = tail.next

Update the tail to the newly added node.

6. Attach Remaining Nodes
tail.next = list1 or list2

When one list becomes empty, attach the remaining part of the other list.

7. Return Result
return dummy.next

dummy.next points to the head of the merged list
We skip the dummy node itself
Example Walkthrough

Input:

list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4

Steps:

Compare 1 and 1, take one of them
Continue comparing and attaching smaller elements
Eventually merge both lists

Output:

1 -> 1 -> 2 -> 3 -> 4 -> 4
Why This Approach is Used

This method is efficient because:

It processes each node exactly once
It does not create new nodes, only rearranges pointers
The dummy node simplifies edge cases like empty lists
Time and Space Complexity

Time complexity is O(n + m), where n and m are the lengths of the two lists.

Space complexity is O(1) since no extra space is used apart from pointers.