How to Solve: Merge Two Sorted Lists

How to Solve: Merge Two Sorted Lists

(A Complete FAANG-Level Interview Guide)

? Introduction

"This problem appears in 1 out of every 3 Linked List interviews—mastering it proves you can handle pointers, edge cases, and in-place modifications under pressure. Nail it, and you’ll stand out as a candidate who writes clean, efficient code."

? WHAT YOU NEED TO KNOW FIRST

Before diving in, ensure you understand: 1. Linked List Basics – How nodes are structured (val, next), traversal, and pointer manipulation. 2. Two-Pointer Technique – Using two pointers to traverse or compare elements efficiently. 3. Dummy Node Pattern – A sentinel node to simplify edge cases (e.g., empty lists).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Repeat this checklist for every "Merge Two Sorted Lists" problem:

1. Clarify Inputs
2. Are the lists singly linked? (Assume yes unless told otherwise.)
3. Can they be empty? (Yes—handle null/None.)

4. Are they strictly sorted? (Assume ascending unless specified.)

5. Choose a Strategy

6. Iterative + Dummy Node (Recommended: O(1) space, clean code).

7. Recursive (Simpler but O(n) stack space—use only if allowed).

8. Initialize Pointers

9. Create a dummy node (ListNode(0)) to simplify edge cases.

10. Set a tail pointer to build the merged list (tail = dummy).

11. Traverse and Compare

12. While both lists have nodes:

    • Compare l1.val and l2.val.
    • Attach the smaller node to tail.next.
    • Move the corresponding list pointer (l1 = l1.next or l2 = l2.next).
    • Move tail forward (tail = tail.next).

13. Attach Remaining Nodes

14. If one list is exhausted, attach the rest of the other list to tail.next.

15. Return the Result

16. The merged list starts at dummy.next.

17. Test Edge Cases

18. Both lists empty → Return null.
19. One list empty → Return the other list.
20. Single-node lists → Verify correct merge.

? WORKED EXAMPLES

Example 1 – Basic: Merge Two Sorted Lists (LeetCode 21)

Problem: Merge two sorted linked lists into one sorted list.

Thought Process

1. Clarify: Lists are singly linked, sorted in ascending order, and may be empty.
2. Strategy: Iterative + Dummy Node (O(1) space).
3. Initialize: dummy = ListNode(0), tail = dummy.
4. Traverse: Compare l1 and l2, attach smaller node to tail.
5. Attach Remaining: tail.next = l1 if l1 else l2.
6. Return: dummy.next.

Code (Python)

class ListNode:

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

        self.val = val

        self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:

    dummy = ListNode(0)  # Dummy node to simplify edge cases

    tail = dummy


    while l1 and l2:

        if l1.val < l2.val:

            tail.next = l1

            l1 = l1.next

        else:

            tail.next = l2

            l2 = l2.next

        tail = tail.next


    # Attach remaining nodes

    tail.next = l1 if l1 else l2

    return dummy.next

Complexity

• Time: O(n + m) → Traverse both lists once.
• Space: O(1) → Only a few pointers used.

Why This Works

• The dummy node avoids null checks for the head of the merged list.
• Two-pointer traversal ensures we always pick the smallest available node.
• Early termination optimizes the remaining nodes attachment.

Example 2 – Medium: Merge k Sorted Lists (LeetCode 23)

Problem: Merge k sorted linked lists into one sorted list.

Twist

• Instead of 2 lists, we have k lists. A brute-force approach (merging one by one) would be O(k²n), which is inefficient.

Thought Process

1. Clarify: k lists, each sorted, may be empty.
2. Strategy: Use a min-heap to always pick the smallest node in O(log k) time.
3. Initialize: Push the first node of each list into a min-heap.
4. Traverse: Pop the smallest node, attach to tail, and push its next node into the heap.
5. Return: dummy.next.

Code (Python)

import heapq

def mergeKLists(lists):

    dummy = ListNode(0)

    tail = dummy

    heap = []


    # Push the first node of each list into the heap

    for i, node in enumerate(lists):

        if node:

            heapq.heappush(heap, (node.val, i, node))


    while heap:

        val, i, node = heapq.heappop(heap)

        tail.next = node

        tail = tail.next

        if node.next:

            heapq.heappush(heap, (node.next.val, i, node.next))


    return dummy.next

Complexity

• Time: O(n log k) → Each node is pushed/popped from the heap once.
• Space: O(k) → Heap stores at most k nodes.

Why This Works

• The min-heap ensures we always pick the smallest node in O(log k) time.
• Index i in the heap tuple breaks ties when values are equal (Python’s heapq is not stable).

Example 3 – Hard/Follow-Up: Merge Two Lists In-Place with O(1) Space

Problem: Merge two sorted lists in-place (no extra space, not even a dummy node).

Twist

• Cannot use a dummy node (must handle the head manually).
• Must rewire pointers without creating new nodes.

Thought Process

1. Clarify: Lists are sorted, may be empty, and must merge in-place.
2. Strategy: Use the smaller head as the starting point, then merge the rest.
3. Initialize: Compare l1 and l2 to set the head.
4. Traverse: Use a prev pointer to build the merged list.
5. Attach Remaining: Link the remaining nodes.

Code (Python)

def mergeTwoListsInPlace(l1: ListNode, l2: ListNode) -> ListNode:

    if not l1:

        return l2

    if not l2:

        return l1


    # Choose the smaller head as the starting point

    if l1.val > l2.val:

        l1, l2 = l2, l1


    head = l1

    prev = None


    while l1 and l2:

        if l1.val <= l2.val:

            prev = l1

            l1 = l1.next

        else:

            # Insert l2's node after prev

            next_node = l2.next

            prev.next = l2

            l2.next = l1

            prev = l2

            l2 = next_node


    # Attach remaining nodes

    if l2:

        prev.next = l2


    return head

Complexity

• Time: O(n + m) → Traverse both lists once.
• Space: O(1) → No extra space used.

Why This Works

• In-place modification rewires next pointers without creating new nodes.
• Head selection ensures the merged list starts with the smallest node.
• Prev pointer keeps track of the last node in the merged list.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. When you see ‘Merge Two Sorted Lists,’ remember:

1. Use a dummy node to avoid null checks—it’s your best friend.
2. Two pointers traverse both lists, always picking the smaller node.
3. Attach remaining nodes in one step—no need to loop further.
4. Edge cases first: Empty lists, single-node lists, and equal values.
5. For k lists, switch to a min-heap for O(n log k) time.

Write the code iteratively first—it’s cleaner and O(1) space. If they ask for recursion, you’ve got that too. Test with empty lists, and you’re golden. Now go crush that interview!

? Final Notes

• Practice Variations: Try merging lists with duplicates, descending order, or circular lists (if the interviewer throws a curveball).
• Whiteboard Tips: Draw the lists, label pointers (l1, l2, tail), and simulate the merge step-by-step.
• Time Yourself: Aim for <10 minutes to code the iterative solution with edge cases.

You’ve got this! ?