Reverse Linked List II (Sublist)

▶

Steps

setup

Initial Setup: Original List

The linked list is initialized with nodes 1 → 2 → 3 → 4 → 5. The algorithm is called with left=2 and right=4 to reverse the sublist from node 2 to node 4.

💡 Understanding the initial list and parameters is essential before any recursion or reversal begins.

Line:

new_head = reverseBetween(nodes[0], 2, 4)

💡 The problem is to reverse only the sublist between positions 2 and 4, leaving other nodes unchanged.

traverse

Recursive Call: Move head forward (left=2 → 1)

Since left > 1, the function calls itself recursively with head.next (node 2), left decremented to 1, and right decremented to 3. This moves the focus closer to the sublist start.

💡 Recursion moves the head pointer forward until left equals 1, isolating the sublist start for reversal.

Line:

return reverseBetween(head.next, left - 1, right - 1)

💡 The recursion shifts the problem to reversing the sublist starting at the new head with updated indices.

fill_row

Base Case Reached: left == 1, Start Reversing First n=3 Nodes

Now left equals 1, so the algorithm calls reverseN to reverse the first n = right - left + 1 = 3 nodes starting from current head (node 2).

💡 Reversing the first n nodes from this point reverses the targeted sublist in place.

Line:

return reverseN(head, right)

💡 The problem reduces to reversing the first n nodes of the current list segment.

fill_cells

reverseN Base Case: n == 1, Mark Successor

When n equals 1, reverseN sets the global successor pointer to head.next (node 5) and returns the current head (node 2) as the last node of the reversed sublist.

💡 Marking the successor node is crucial to reconnect the reversed sublist back to the remainder of the list.

Line:

if n == 1:
    successor = head.next
    return head

💡 The successor node is the first node after the reversed sublist, needed for reconnection.

fill_cells

Recursive Step: reverseN called for n=2 on node 3

reverseN recursively calls itself with head.next (node 3) and n decremented to 2, continuing reversal deeper into the sublist.

💡 Each recursive call moves one node deeper, building the reversed list from the end back up.

Line:

last = reverseN(head.next, n - 1)

💡 The recursion unwinds after reaching the base case, reversing links on the way back.

fill_cells

Recursive Step: reverseN called for n=3 on node 4

reverseN recursively calls itself with head.next (node 4) and n decremented to 1, reaching the base case for this call.

💡 This call will hit the base case next, marking the successor and starting to reverse links.

Line:

last = reverseN(head.next, n - 1)

💡 The recursion continues until the base case is reached at the last node to reverse.

reverse_link

Unwinding Recursion: Reverse Link from node 4 to node 3

As recursion unwinds, head.next.next is set to head, reversing the link from node 3 → 4 to 4 → 3. Then head.next is set to successor (node 5) to reconnect the tail.

💡 This step reverses the link between two nodes and reconnects the reversed sublist to the rest of the list.

Line:

head.next.next = head
head.next = successor

💡 Reversing links during recursion unwind flips the sublist nodes in place.

reverse_link

Unwinding Recursion: Reverse Link from node 3 to node 2

Next, head.next.next is set to head, reversing the link from node 2 → 3 to 3 → 2. Then head.next is set to successor (node 5) to maintain the connection.

💡 Continuing to reverse links during recursion unwind completes the sublist reversal.

Line:

head.next.next = head
head.next = successor

💡 Each recursion unwind reverses one link, building the reversed sublist from the end to the start.

reconstruct

Return Reversed Sublist Head (node 4) to Previous Recursive Call

reverseN returns the last node of the reversed sublist (node 4) up the recursion stack. The previous reverseBetween call sets head.next to this reversed sublist head.

💡 Returning the new head of the reversed sublist allows the upper recursion level to reconnect the reversed segment.

Line:

return last
head.next = reverseBetween(head.next, left - 1, right - 1)

💡 The reversed sublist head replaces the original sublist start in the main list.

reconstruct

Final State: Fully Reversed Sublist Connected

The reversed sublist 4 → 3 → 2 is connected back to node 1 at the front and node 5 at the end, resulting in the final list 1 → 4 → 3 → 2 → 5.

💡 The algorithm completes by returning the original head, now pointing to the reversed sublist segment.

Line:

return head

💡 The sublist reversal is done in place, preserving the rest of the list structure.

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

successor = None

def reverseN(head, n):
    global successor
    if n == 1:  # STEP 4: base case, mark successor
        successor = head.next
        return head
    last = reverseN(head.next, n - 1)  # STEP 5-6: recurse deeper
    head.next.next = head  # STEP 7-8: reverse link
    head.next = successor
    return last  # STEP 9: return reversed sublist head

def reverseBetween(head, left, right):
    if left == 1:  # STEP 3: base case to reverse first n nodes
        return reverseN(head, right)
    head.next = reverseBetween(head.next, left - 1, right - 1)  # STEP 2: recurse to sublist start
    return head  # STEP 10: reconnect and return

# Driver code
if __name__ == '__main__':
    nodes = [ListNode(i) for i in range(1, 6)]
    for i in range(4):
        nodes[i].next = nodes[i+1]
    new_head = reverseBetween(nodes[0], 2, 4)  # STEP 1: initial call
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

📊

Reverse Linked List II (Sublist) - Watch the Algorithm Execute, Step by Step

Watching each pointer move and recursive call helps you understand how the sublist is reversed in place without extra memory.

advance

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

fill_row

1

→

2

→

3

→

4

→

5

fill_cells

1

→

2

→

3

→

4

→

5

fill_cells

1

→

2

→

3

→

4

→

5

fill_cells

1

→

2

→

3

→

4

→

5

reverse_link

1

→

2

→

3

→

4

→

5

reverse_link

1

→

2

→

3

→

4

→

5

reconstruct

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

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

Key Takeaways

✓ The recursive approach isolates the sublist start by moving the head pointer forward until left equals 1.

This is hard to see in code alone because the recursion hides the pointer movement; visualization shows exactly how the head moves.

✓ Reversing the first n nodes uses recursion to reverse links on the way back up the call stack.

Understanding reversal during recursion unwind is tricky without seeing each link reversal step explicitly.

✓ The successor pointer marks the node immediately after the reversed sublist, enabling correct reconnection.

This subtle pointer is critical for correctness but easy to overlook when reading code.

Practice

1. You are given two non-empty singly linked lists representing two non-negative integers. The digits are stored in forward order, with the most significant digit at the head. You need to add the two numbers and return the sum as a linked list in the same forward order. Which approach guarantees an optimal solution without modifying the input lists or using extra space proportional to the number of digits?

easy

A. Reverse both lists, add digits from least significant to most significant, then reverse the result.

B. Use a greedy approach to add digits from left to right without padding or recursion.

C. Pad the shorter list with zeros, recursively add corresponding nodes from the most significant digit, and propagate carry backward.

D. Convert both lists to integers, add them, then convert the sum back to a linked list.

Solution

1. Step 1: Understand the problem constraints

   The digits are stored in forward order, so addition must start from the most significant digit. Direct addition from head to tail requires alignment of list lengths.

2. Step 2: Identify the approach that handles alignment and carry correctly

   Padding the shorter list ensures both lists have equal length. Recursively adding nodes from the most significant digit allows carry to propagate backward naturally without reversing or extra space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Padding + recursion handles carry and alignment correctly [OK]

Hint: Pad shorter list and recurse from MSB [OK]

Common Mistakes:

• Reversing lists modifies inputs unexpectedly
• Greedy addition fails due to carry propagation
• Converting to integers causes overflow or inefficiency

2. Consider the following Python code implementing the optimal merge K sorted lists approach using a min-heap. Given the input lists: [1->4->5], [1->3->4], [2->6], what is the value of current.next.val after the third iteration of the while loop?

easy

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Initialize heap with heads: 1,1,2

   Heap order: [1,1,2]

2. Step 2: Iterations of while loop

   1st pop: smallest=1 (from first list), push 4; 2nd pop: smallest=1 (from second list), push 3; 3rd pop: smallest=2 (from third list), push 6. After 3rd iteration, current.next.val = 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Third extracted node value is 2 [OK]

Hint: Track heap pops and pushed next nodes carefully [OK]

Common Mistakes:

• Off-by-one iteration counting
• Confusing which node is popped
• Forgetting to push next nodes

3. You are given a singly linked list with unsorted integer values. You need to sort the list in ascending order with O(n log n) time complexity and O(1) auxiliary space. Which algorithmic approach best fits this requirement?

easy

A. Perform a bottom-up iterative merge sort directly on the linked list without extra arrays.

B. Use a recursive quicksort on the linked list by partitioning around a pivot node.

C. Extract all values into an array, sort the array using quicksort, then rebuild the linked list.

D. Apply a greedy insertion sort by inserting nodes into a new sorted list one by one.

Solution

1. Step 1: Understand time and space constraints

   The problem requires O(n log n) time and O(1) auxiliary space, which rules out array extraction and recursive approaches that use extra space.

2. Step 2: Identify algorithm matching constraints

   Bottom-up iterative merge sort on linked lists achieves O(n log n) time and O(1) space by merging sublists iteratively without recursion or extra arrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bottom-up merge sort is the standard in-place linked list sorting method [OK]

Hint: Bottom-up merge sort is in-place and O(n log n) [OK]

Common Mistakes:

• Thinking quicksort is efficient on linked lists due to lack of random access
• Assuming insertion sort is efficient for large lists
• Believing array extraction is O(1) space

4. What is the space complexity of the recursive approach to remove the nth node from the end of a singly linked list of length n?

medium

A. O(1) -- constant extra space since no data structures are used

B. O(n) -- due to recursion stack frames for each node

C. O(log n) -- recursion depth is logarithmic due to divide and conquer

D. O(n) -- due to auxiliary arrays used to store node references

Solution

1. Step 1: Identify recursion depth

   Recursion visits each node once, so recursion stack depth is n.

2. Step 2: Analyze space usage

   No extra arrays or data structures are used, but recursion stack frames consume O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion stack space grows linearly with list length [OK]

Hint: Recursion stack space equals max call depth [OK]

Common Mistakes:

• Assuming constant space for recursion
• Confusing recursion with iterative approach
• Thinking recursion depth is logarithmic

5. What is the time complexity of the optimal linked list rotation algorithm that uses two pointers and connects the tail to the head to form a circular list before breaking it at the new tail?

medium

A. O(n), where n is the length of the list

B. O(k * n), where k is the rotation count and n is the list length

C. O(n + k), where n is list length and k is rotation count

D. O(n^2), due to nested pointer traversals

Solution

1. Step 1: Identify main operations

   Traversing the list once to find length and tail is O(n).

2. Step 2: Pointer movements

   Moving fast pointer k steps and slow pointer until fast reaches tail is at most O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All operations combined are linear in n [OK]

Hint: Length calculation + single pass pointer moves -> O(n) [OK]

Common Mistakes:

• Assuming O(k*n) due to repeated rotations
• Confusing k with n in complexity
• Thinking nested loops cause O(n^2)