Here is solutions for Merge Two Sorted Linked Lists.

1. Understand the Problem

• You are given two linked lists (list1 and list2) that are already sorted in non-decreasing order.

👉 The goal is to merge them into one sorted linked list, also in non-decreasing order. Return the head of the new merged list.

2. Clarify Constraints – Ask 4–5 Questions

1. Can the lists be empty?

=> Yes, either list may be None.

1. Are the linked lists guaranteed to be sorted?

=> Yes, both input lists are sorted in ascending order.

1. Can we modify the existing nodes or must we create new nodes?

=> We can reuse the existing nodes (preferable to reduce memory).

1. What is the expected time and space complexity?

=> Time: O(n + m), Space: O(1) (excluding output list).

1. What if both lists consist of equal values (e.g., [1,1,1] and [1,1])?

=> Still merge preserving full list order.

3. Explore Examples

4. Brainstorm 2-3 solutions

4.1. Naive solution, rebuild all the list - Time: O((n + m))*log(n + m), Space: O(n + m)

• Build a new array size n + m.

• Sort all of this => Build a new list.

• Time: O((n + m))*log(n + m)

• Space: O(n + m)

4.2. Optimize solution, merge sort - Time: O(n + m), Space: O(n + m)

• Build a size n + m.

• Apply two pointers to merge sort.

• Time: O(n + m).

• Space: O(n + m).

4.3. Dummy node - Time: O(n + m), Space: O(1)

• Use dummy node to store to the address of the node in list1, list2, based on value.

• Time: O(n + m).

• Space: O(1).

5. Implement solutions

5.1. Recursive Solution - Time: O(N + M), Space: O(N + M), same with logic create new array

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        if list2 is None:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

• Time: O(N + M).

• Space: O(N + M).

5.2. Dummy Node - Time: O(N + M), Space: O(1)

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

        # Attach remaining nodes
        if list1:
            current.next = list1
        else:
            current.next = list2

        return dummy.next

• Time: O(N + M).

• Space: O(1).

6. Dry run examples

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