Reverse Linked List

▶

Steps

setup

Initialize pointers for recursion

We start the reversal by calling the helper function with prev = null and curr = head (node with value 1). This sets up the initial state for recursion.

💡 Setting prev to null means the reversed list is initially empty; curr points to the first node to process.

Line:

return helper(None, head)

💡 The reversal process begins with no reversed nodes and the full original list to process.

compare

Check if current node is null (node 1)

The helper function checks if curr is null. Since curr points to node 1, it is not null, so we proceed to reverse the pointer.

💡 This base case check stops recursion when the list end is reached.

Line:

if not curr:
    return prev

💡 The recursion continues as long as there are nodes to process.

reverse_link

Save next node and reverse current node's next pointer (node 1)

We save curr.next (node 2) into next_temp to keep track of the next node before changing curr.next. Then we reverse the link by setting curr.next to prev (which is null). This detaches node 1 from node 2 and points it backward.

💡 Saving next node is crucial because curr.next will be overwritten during reversal. Reversing the pointer flips the list direction one node at a time.

Line:

next_temp = curr.next
curr.next = prev

💡 Preserving the next node allows the recursion to continue correctly after reversing the pointer. After this step, node 1 points backward to null, starting the reversed list.

traverse

Recurse with updated pointers (prev=1, curr=2)

We recurse by calling helper with prev = curr (node 1) and curr = next_temp (node 2), moving forward in the list.

💡 Updating pointers for recursion moves the reversal process one node ahead.

Line:

return helper(curr, next_temp)

💡 The reversed list now includes node 1, and the remaining list starts at node 2.

reverse_link

Check if current node is null and reverse next pointer (node 2)

At node 2, we check if curr is null. It is not, so we save curr.next (node 3) into next_temp and reverse curr.next to point to prev (node 1), so node 2 now points back to node 1.

💡 The base case check ensures recursion stops only at the list end. Preserving next node is necessary before pointer reversal.

Line:

if not curr:
    return prev
next_temp = curr.next
curr.next = prev

💡 The recursion continues as nodes remain to be reversed. Node 2 is now connected backward, growing the reversed list.

traverse

Recurse with updated pointers (prev=2, curr=3)

We recurse with prev = curr (node 2) and curr = next_temp (node 3), moving forward in the list.

💡 This moves the reversal process forward by one node.

Line:

return helper(curr, next_temp)

💡 The reversed list now includes nodes 2->1, and the remaining list starts at node 3.

reverse_link

Check if current node is null and reverse next pointer (node 3)

At node 3, we check if curr is null. It is not, so we save curr.next (node 4) into next_temp and reverse curr.next to point to prev (node 2), so node 3 now points back to node 2.

💡 The base case check ensures recursion stops only at the list end. Preserving next node is necessary before pointer reversal.

Line:

if not curr:
    return prev
next_temp = curr.next
curr.next = prev

💡 The recursion continues as nodes remain to be reversed. Node 3 is now connected backward, growing the reversed list.

traverse

Recurse with updated pointers (prev=3, curr=4)

We recurse with prev = curr (node 3) and curr = next_temp (node 4), moving forward in the list.

💡 This moves the reversal process forward by one node.

Line:

return helper(curr, next_temp)

💡 The reversed list now includes nodes 3->2->1, and the remaining list starts at node 4.

reverse_link

Check if current node is null and reverse next pointer (node 4)

At node 4, we check if curr is null. It is not, so we save curr.next (node 5) into next_temp and reverse curr.next to point to prev (node 3), so node 4 now points back to node 3.

💡 The base case check ensures recursion stops only at the list end. Preserving next node is necessary before pointer reversal.

Line:

if not curr:
    return prev
next_temp = curr.next
curr.next = prev

💡 The recursion continues as nodes remain to be reversed. Node 4 is now connected backward, growing the reversed list.

traverse

Recurse with updated pointers (prev=4, curr=5)

We recurse with prev = curr (node 4) and curr = next_temp (node 5), moving forward in the list.

💡 This moves the reversal process forward by one node.

Line:

return helper(curr, next_temp)

💡 The reversed list now includes nodes 4->3->2->1, and the remaining list starts at node 5.

reverse_link

Check if current node is null and reverse next pointer (node 5)

At node 5, we check if curr is null. It is not, so we save curr.next (null) into next_temp and reverse curr.next to point to prev (node 4), so node 5 now points back to node 4.

💡 The base case check ensures recursion stops only at the list end. Preserving next node is necessary before pointer reversal.

Line:

if not curr:
    return prev
next_temp = curr.next
curr.next = prev

💡 The recursion continues as nodes remain to be reversed. Node 5 is now connected backward, completing the reversed list.

reconstruct

Recurse with updated pointers (prev=5, curr=null) and return reversed list head

We recurse with prev = curr (node 5) and curr = next_temp (null). Since curr is null, recursion stops and returns prev as new head. The reversal is complete.

💡 This step reaches the base case, ending recursion and returning the reversed list's head to the caller.

Line:

return helper(curr, next_temp)
if not curr:
    return prev

💡 The reversed list head is node 5, the last processed node, confirming the reversal is done.

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

def reverseList(head):
    def helper(prev, curr):
        if not curr:  # STEP 2,6,10,14,18,22
            return prev
        next_temp = curr.next  # STEP 3,7,11,15,19
        curr.next = prev  # STEP 4,8,12,16,20
        return helper(curr, next_temp)  # STEP 5,9,13,17,21
    return helper(None, head)  # STEP 1

# Driver code
if __name__ == '__main__':
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    new_head = reverseList(head)
    curr = new_head
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

📊

Reverse Linked List - Watch the Algorithm Execute, Step by Step

Watching each pointer change and recursive call helps you understand how the list is reversed in-place without extra memory.

advance

1

→

2

→

3

→

4

→

5

compare

1

→

2

→

3

→

4

→

5

reverse_link

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

reverse_link

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

reverse_link

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

reverse_link

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

reverse_link

1

→

2

→

3

→

4

→

5

reconstruct

5

→

4

→

3

→

2

→

1

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

Key Takeaways

✓ Reversing a linked list in-place is done by redirecting each node's next pointer to its predecessor.

This insight is hard to see from code alone because pointer changes happen implicitly; visualization shows explicit pointer redirection.

✓ The recursion uses two pointers, prev and curr, to track the reversed and unreversed parts of the list.

Understanding these pointers' roles clarifies how the algorithm progresses step-by-step.

✓ The base case occurs when curr is null, signaling the end of the original list and the start of returning the reversed list head.

Seeing the base case visually helps understand when and why recursion stops.

Practice

1. You are given a singly linked list and an integer k. The task is to rotate the list to the right by k places. Which of the following approaches guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Repeatedly move the last node to the front k times, each time traversing the list to find the last node.

B. Reverse the entire list, then reverse the first k nodes and the remaining nodes separately.

C. Use a dynamic programming approach to store intermediate rotations and reuse them to build the final rotated list.

D. Calculate the length of the list, connect the tail to the head to form a circular list, then find the new tail using two pointers and break the circle.

Solution

1. Step 1: Understand the problem constraints

   Rotating a linked list by k places requires rearranging nodes efficiently without extra space.

2. Step 2: Identify the optimal approach

   Calculating length and connecting tail to head forms a circular list, then using two pointers to find the new tail and breaking the circle achieves O(n) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal approach uses length calculation and two pointers [OK]

Hint: Optimal rotation uses length + two pointers [OK]

Common Mistakes:

• Using repeated single rotations leads to O(n*k) time
• Misapplying DP or reversal techniques that don't fit linked list rotation

2. You are given a singly linked list and asked to swap every two adjacent nodes, returning the modified list. Which approach guarantees an optimal solution that swaps nodes in-place without extra data structures and handles all edge cases efficiently?

easy

A. Use a greedy approach that swaps values instead of nodes to minimize pointer changes.

B. Use a recursive approach that swaps pairs by adjusting pointers and recurses on the rest of the list.

C. Use dynamic programming to store intermediate swapped sublists for reuse.

D. Use a brute force approach that creates a new list and inserts nodes in swapped order.

Solution

1. Step 1: Understand the problem constraints

   The problem requires swapping nodes in pairs by changing pointers, not just values, and must be done in-place.

2. Step 2: Identify the approach that swaps nodes recursively

   The recursive approach swaps the first two nodes, then recursively swaps the rest, ensuring all pairs are swapped correctly without extra space for new lists.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Recursive pointer swapping matches problem requirements [OK]

Hint: Recursive pointer swapping fits in-place pairwise node swaps [OK]

Common Mistakes:

• Thinking swapping values is sufficient
• Using DP unnecessarily
• Creating new lists wastes space

3. Given the following recursive code for swapping nodes in pairs, what is the output when the input list is 1 -> 2 -> 3 -> null?

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

def swapPairs(head: ListNode) -> ListNode:
    def helper(node):
        if not node or not node.next:
            return node
        first = node
        second = node.next
        first.next = helper(second.next)
        second.next = first
        return second
    return helper(head)

# Input list: 1 -> 2 -> 3 -> null

What is the printed output after swapping pairs?

easy

A. 2 3 1

B. 1 3 2

C. 2 1 3

D. 3 2 1

Solution

1. Step 1: Trace helper on node with val=1

   First = 1, Second = 2; recursively call helper on node with val=3.

2. Step 2: Trace helper on node with val=3

   Node 3 has no next, so return node 3 as is.

3. Step 3: Complete first call

   Set first.next = node 3, second.next = first (1), return second (2). Resulting list: 2 -> 1 -> 3.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Output matches expected swapped pairs [OK]

Hint: Recursive swaps pairs, last odd node remains [OK]

Common Mistakes:

• Swapping values instead of nodes
• Misplacing last node in odd-length list

4. The following code attempts to merge two sorted linked lists in-place:

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val > l2.val:
        l1, l2 = l2, l1
    head = l1
    while l1 and l2:
        prev = None
        while l1 and l1.val <= l2.val:
            prev = l1
            # BUG: Missing l1 pointer advancement here
        prev.next = l2
        l1, l2 = l2, l1
    return head

What is the bug in this code?

medium

A. Swapping l1 and l2 when l1.val > l2.val is incorrect

B. Not initializing prev before inner while loop causes NoneType error

C. Returning head instead of l1 or l2 at the end causes wrong output

D. Line missing advancement of l1 inside inner while loop causes infinite loop

Solution

1. Step 1: Identify the inner while loop behavior

   The inner loop should advance l1 pointer to traverse nodes with values <= l2.val. Missing l1 = l1.next causes infinite loop.

2. Step 2: Confirm impact of missing advancement

   Without advancing l1, prev remains the same, loop never ends, causing infinite loop or crash.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing l1 advancement inside inner loop causes infinite loop [OK]

Hint: Always advance pointers inside loops to avoid infinite loops [OK]

Common Mistakes:

• Confusing swap of l1 and l2 as bug
• Thinking return head is incorrect
• Assuming prev initialization causes error

5. The following code attempts to rotate a linked list to the right by k places. Identify the line that contains a subtle bug that can cause the list to become cyclic or truncated incorrectly.

medium

A. Line: tail.next = head # make circular

B. Line: slow.next = slow # BUG: incorrect break causing cycle

C. Line: for _ in range(k): fast = fast.next

D. Line: k = k % length

Solution

1. Step 1: Understand the purpose of breaking the list

   After rotation, the list must be broken at the new tail by setting slow.next = None.

2. Step 2: Identify the bug

   The original code sets slow.next = slow, which creates a cycle instead of breaking the list.

3. Step 3: Correct fix

   Change to slow.next = None to properly break the list.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Correct break is slow.next = None [OK]

Hint: Break list by setting slow.next = None [OK]

Common Mistakes:

• Setting slow.next to itself or wrong node causing cycles
• Not handling k modulo length correctly
• Forgetting to make list circular before rotation