Merge Two Sorted Lists

▶

Steps

setup

Check if list1 is empty

We check if list1 is empty. Since list1 starts with value 1, it is not empty, so we proceed.

💡 This step handles edge cases where one list is empty, returning the other immediately.

Line:

if not l1:
    return l2

💡 Ensures the algorithm handles empty input lists gracefully.

setup

Check if list2 is empty

We check if list2 is empty. Since list2 starts with value 1, it is not empty, so we proceed.

💡 This step ensures the algorithm can handle the case where list2 is empty.

Line:

if not l2:
    return l1

💡 Both lists are non-empty, so merging is needed.

setup

Determine head of merged list

Compare the first nodes of l1 and l2. Both have value 1, but since l1.val <= l2.val, head is set to l1.

💡 Choosing the head node sets the starting point of the merged list and simplifies pointer management.

Line:

if l1.val > l2.val:
    l1, l2 = l2, l1
head = l1

💡 The merged list starts with the smaller or equal first node of the two lists.

traverse

Start merging loop: initialize prev to None

We enter the main loop to merge lists. 'prev' is initialized to None to track the last node from l1 before insertion.

💡 Tracking 'prev' helps to insert nodes from l2 into l1 correctly.

Line:

while l1 and l2:
    prev = None

💡 We prepare to traverse and merge nodes step-by-step.

traverse

Advance l1 while l1.val <= l2.val

l1.val (1) <= l2.val (1), so move prev to l1 (node 1), and advance l1 to next node (2).

💡 We move forward in l1 as long as its nodes are smaller or equal to l2's current node.

Line:

while l1 and l1.val <= l2.val:
    prev = l1
    l1 = l1.next

💡 We find the correct insertion point for l2's current node.

insert

Insert l2 node after prev

We link prev.next to l2 (node with val 1), inserting l2's node into l1's chain.

💡 This step merges the smaller l2 node into the merged list by pointer reassignment.

Line:

prev.next = l2

💡 Pointer manipulation merges nodes without extra space.

traverse

Swap l1 and l2 pointers

Swap l1 and l2 pointers so that l1 always points to the smaller current node for next iteration.

💡 Swapping pointers simplifies the logic by always advancing the smaller list.

Line:

l1, l2 = l2, l1

💡 This clever swap avoids extra conditionals and keeps code concise.

traverse

Advance l1 while l1.val <= l2.val

l1.val (1) <= l2.val (2), move prev to l1 (node 4), advance l1 to next node (3).

💡 We continue advancing l1 to find the correct insertion point for l2's current node.

Line:

while l1 and l1.val <= l2.val:
    prev = l1
    l1 = l1.next

💡 We keep l1 pointer moving forward while its nodes are smaller or equal.

insert

Insert l2 node after prev

Link prev.next (node 4) to l2 (node 2), inserting l2's node with val 2 into merged list.

💡 We insert the smaller l2 node into the merged list by pointer reassignment.

Line:

prev.next = l2

💡 Pointer manipulation merges nodes without extra space.

traverse

Swap l1 and l2 pointers

Swap l1 and l2 pointers again to keep l1 pointing to smaller current node for next iteration.

💡 Swapping pointers keeps the merging logic consistent and simple.

Line:

l1, l2 = l2, l1

💡 This swap is key to the in-place merge without dummy nodes.

traverse

Advance l1 while l1.val <= l2.val

l1.val (2) <= l2.val (3), move prev to l1 (node 2), advance l1 to next node (3).

💡 We continue advancing l1 to find the correct insertion point for l2's current node.

Line:

while l1 and l1.val <= l2.val:
    prev = l1
    l1 = l1.next

💡 We keep l1 pointer moving forward while its nodes are smaller or equal.

insert

Insert l2 node after prev

Link prev.next (node 2) to l2 (node 5 with val 3), inserting l2's node into merged list.

💡 We insert the smaller l2 node into the merged list by pointer reassignment.

Line:

prev.next = l2

💡 Pointer manipulation merges nodes without extra space.

traverse

Swap l1 and l2 pointers

Swap l1 and l2 pointers again to keep l1 pointing to smaller current node for next iteration.

💡 Swapping pointers keeps the merging logic consistent and simple.

Line:

l1, l2 = l2, l1

💡 This swap is key to the in-place merge without dummy nodes.

traverse

Advance l1 while l1.val <= l2.val

l1.val (3) <= l2.val (4), move prev to l1 (node 5), advance l1 to next node (6).

💡 We continue advancing l1 to find the correct insertion point for l2's current node.

Line:

while l1 and l1.val <= l2.val:
    prev = l1
    l1 = l1.next

💡 We keep l1 pointer moving forward while its nodes are smaller or equal.

insert

Insert l2 node after prev

Link prev.next (node 5) to l2 (node 3 with val 4), inserting l2's node into merged list.

💡 We insert the smaller l2 node into the merged list by pointer reassignment.

Line:

prev.next = l2

💡 Pointer manipulation merges nodes without extra space.

traverse

Swap l1 and l2 pointers

Swap l1 and l2 pointers again to keep l1 pointing to smaller current node for next iteration.

💡 Swapping pointers keeps the merging logic consistent and simple.

Line:

l1, l2 = l2, l1

💡 This swap is key to the in-place merge without dummy nodes.

traverse

Advance l1 while l1.val <= l2.val

l1.val (4) <= l2.val (4), move prev to l1 (node 3), advance l1 to next node (null).

💡 We advance l1 until it reaches the end or finds a node greater than l2's current node.

Line:

while l1 and l1.val <= l2.val:
    prev = l1
    l1 = l1.next

💡 We reach the end of l1, preparing to append remaining l2 nodes.

insert

Attach remaining l2 nodes

Since l1 is null, link prev.next (node 3) to l2 (node 6), appending remaining nodes from l2.

💡 Appending remaining nodes completes the merge when one list is exhausted.

Line:

prev.next = l2

💡 No more comparisons needed; remaining nodes are already sorted.

traverse

End of merging loop

l1 is null, so the while loop ends. The merged list head is returned.

💡 Loop ends when one list is fully merged; the other list is appended.

Line:

return head

💡 The merged list is fully constructed in sorted order.

reconstruct

Final merged list

The final merged linked list is [1,1,2,3,4,4], combining nodes from both input lists in sorted order.

💡 This final step confirms the merge result matches the expected sorted order.

Line:

return head

💡 The in-place merge successfully combined both lists without extra space.

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

def mergeTwoLists(l1, l2):
    # STEP 1
    if not l1:
        return l2
    # STEP 2
    if not l2:
        return l1
    # STEP 3
    if l1.val > l2.val:
        l1, l2 = l2, l1
    head = l1
    # STEP 4
    while l1 and l2:
        prev = None
        # STEP 5
        while l1 and l1.val <= l2.val:
            prev = l1
            l1 = l1.next
        # STEP 6
        prev.next = l2
        # STEP 7
        l1, l2 = l2, l1
    # STEP 19
    return head

📊

Merge Two Sorted Lists - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and node comparison helps you understand the in-place merging logic clearly, which is hard to grasp from code alone.

advance

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

compare

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

connect

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

connect

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

connect

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

connect

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

connect

1

→

2

→

4

→

1

→

3

→

4

advance

1

→

2

→

4

→

1

→

3

→

4

Result: [1, 1, 2, 3, 4, 4]

reconstruct

1

→

1

→

2

→

3

→

4

→

4

Result: [1, 1, 2, 3, 4, 4]

Key Takeaways

✓ In-place merging is achieved by clever pointer swaps and insertions without extra memory.

This insight is hard to see from code alone because pointer swaps are subtle and happen inside nested loops.

✓ Swapping l1 and l2 pointers after each insertion keeps the algorithm simple and always advances the smaller node.

This technique avoids complex conditionals and makes the code elegant but can be confusing without visualization.

✓ Tracking the 'prev' pointer is essential to insert nodes from l2 into the correct position in l1.

Understanding 'prev' helps clarify how nodes are linked during merging, which is not obvious from code alone.

Practice

1. Consider the following code snippet for adding two numbers represented by linked lists in-place. Given l1 = [2,4,3] and l2 = [5,6,4], what is the value of the node pointed to by prev after the second iteration of the while loop?

easy

A. 0

B. 7

C. 1

D. 9

Solution

1. Step 1: Trace first iteration

   Sum 2 + 5 + 0 = 7, carry=0, l1.val=7, prev points to node with val=7.

2. Step 2: Trace second iteration

   Sum 4 + 6 + 0 = 10, carry=1, l1.val=0, prev updated to node with val=0.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After second iteration, prev.val is 0 [OK]

Hint: Carry affects node value update each iteration [OK]

Common Mistakes:

• Off-by-one error in updating prev
• Ignoring carry in sum calculation
• Confusing l1 and l2 pointers

2. What is the time and space complexity of the recursive approach to reverse a sublist between positions left and right in a singly linked list of length n?

medium

A. Time: O(n), Space: O(1) due to in-place reversal

B. Time: O(n^2), Space: O(n) due to repeated traversals

C. Time: O(right - left), Space: O(right - left) due to partial recursion

D. Time: O(n), Space: O(n) due to recursion stack

Solution

1. Step 1: Analyze time complexity

   The recursive approach visits each node at most once, so time complexity is O(n).

2. Step 2: Analyze space complexity

   Recursion depth can be up to n in worst case, so space complexity is O(n) due to recursion stack.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack space is often overlooked but critical here [OK]

Hint: Recursion adds O(n) space, not O(1) [OK]

Common Mistakes:

• Assuming constant space for in-place reversal
• Confusing partial recursion depth with full list length
• Mistaking time complexity as quadratic

3. What is the time complexity of the optimal iterative approach that reverses nodes in k-groups in a singly linked list of length n? Assume k is a fixed positive integer.

medium

A. O(n log k)

B. O(n * k)

C. O(n / k * k^2)

D. O(n)

Solution

1. Step 1: Identify the number of groups processed

   The list of length n is divided into approximately n/k groups.

2. Step 2: Analyze reversal cost per group

   Each group reversal takes O(k) time, so total time is (n/k) * k = O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Each node is visited and reversed exactly once [OK]

Hint: Reversing fixed-size groups leads to linear time [OK]

Common Mistakes:

• Mistaking O(n * k) by multiplying n and k without division
• Confusing group count and reversal cost per group

4. Suppose you want to delete a node in a singly linked list given only access to that node, but now the node to delete might be the tail node. Which of the following statements is true about the optimal in-place deletion approach that copies the next node's data and deletes the next node?

hard

A. You must traverse from head to delete the tail node since no next node exists.

B. It works perfectly for tail nodes by copying data from a dummy next node.

C. You can delete the tail node by setting its value to None and next to None.

D. It cannot delete the tail node because there is no next node to copy from.

Solution

1. Step 1: Understand the limitation of the approach

   The method copies data from the next node and deletes the next node, so it requires a next node.

2. Step 2: Analyze tail node case

   The tail node has no next node, so this approach cannot be applied to delete the tail node.

3. Step 3: Consider alternatives

   Deleting the tail node requires access to the head to update the previous node's next pointer.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Tail node deletion requires head access, not possible with this method [OK]

Hint: Tail node has no next node to copy from [OK]

Common Mistakes:

• Assuming tail node can be deleted with same method
• Trying to create dummy next node to fix tail deletion
• Setting tail node value to None without pointer updates

5. Suppose the problem is modified so that the linked list is circular (last node points back to head). Which of the following changes is necessary to correctly remove the nth node from the end in one pass?

hard

A. Use the same two-pointer approach without changes; it works as is.

B. First break the circular link to convert it into a linear list, then apply the standard algorithm.

C. Use a hash set to detect the cycle and count nodes before removal.

D. Modify the recursion to detect when the node revisits the head to stop infinite recursion.

Solution

1. Step 1: Understand circular list implications

   In a circular list, traversal never ends naturally, so counting nodes or recursion can loop infinitely.

2. Step 2: Break the cycle

   Temporarily breaking the cycle converts it to a linear list, allowing standard removal algorithms to work correctly.

3. Step 3: Restore circular link if needed

   After removal, reconnect the last node to the new head to restore circularity.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Breaking cycle prevents infinite loops and enables standard logic [OK]

Hint: Circular lists require cycle breaking before linear algorithms [OK]

Common Mistakes:

• Assuming two-pointer works on circular lists
• Using recursion without cycle detection
• Using extra space unnecessarily