How to Solve: Reverse a Linked List (Iterative & Recursive) – Complete Guide for FAANG Interviews

How to Solve: Reverse a Linked List (Iterative & Recursive) – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—mastering it proves you can manipulate pointers, handle edge cases, and think recursively—skills that separate strong candidates from the rest."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Linked List Basics – Node structure (val, next), traversal, and pointer manipulation. 2. Recursion Fundamentals – Call stack, base cases, and recursive decomposition. 3. Time & Space Complexity – Big-O notation for iterative vs. recursive approaches.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Repeat this mental checklist for every linked list reversal problem:

Iterative Approach

1. Initialize 3 pointers:
2. prev = None (will eventually become the new head)
3. curr = head (current node being processed)
4. next = None (temporary storage for the next node)
5. Traverse the list:
6. While curr is not None:
   • Store next = curr.next (save the next node)
   • Reverse the link: curr.next = prev
   • Move prev and curr forward:
   • prev = curr
   • curr = next
7. Return prev (the new head of the reversed list).

Recursive Approach

1. Base Case:
2. If head is None or head.next is None, return head (empty list or single node).
3. Recursive Step:
4. Reverse the rest of the list: new_head = reverseList(head.next)
5. Fix the current node’s link:
6. head.next.next = head (reverse the link)
7. head.next = None (avoid cycles)
8. Return new_head (the new head of the reversed list).

? WORKED EXAMPLES

Example 1 – Basic (Iterative Reversal)

Problem: Reverse a singly linked list iteratively. Input: 1 -> 2 -> 3 -> 4 -> 5 -> None Output: 5 -> 4 -> 3 -> 2 -> 1 -> None

Thought Process

1. Start with prev = None, curr = 1.
2. Traverse:
3. next = 2, 1.next = None, prev = 1, curr = 2
4. next = 3, 2.next = 1, prev = 2, curr = 3
5. ... until curr = None.
6. Return prev (now 5).

Code (Python)

class ListNode:

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

        self.val = val

        self.next = next

def reverseList(head: ListNode) -> ListNode:

    prev, curr = None, head

    while curr:

        next_node = curr.next  # Store next node

        curr.next = prev       # Reverse the link

        prev = curr            # Move prev forward

        curr = next_node       # Move curr forward

    return prev                # New head

Complexity

• Time: O(n) (single pass)
• Space: O(1) (constant extra space)

Why This Works

• We reverse links in-place by flipping next pointers as we traverse.
• prev always points to the new head of the reversed segment.

Example 2 – Medium (Recursive Reversal)

Problem: Reverse a singly linked list recursively. Input: 1 -> 2 -> 3 -> None Output: 3 -> 2 -> 1 -> None

Thought Process

1. Base case: If head is None or head.next is None, return head.
2. Recursively reverse the rest: new_head = reverseList(2 -> 3 -> None) → returns 3 -> 2 -> None.
3. Fix the current node (1):
4. 2.next.next = 1 (now 2 -> 1)
5. 1.next = None (avoid cycle)
6. Return new_head (3).

Code (Python)

def reverseList(head: ListNode) -> ListNode:

    if not head or not head.next:

        return head

    new_head = reverseList(head.next)

    head.next.next = head  # Reverse the link

    head.next = None       # Avoid cycle

    return new_head

Complexity

• Time: O(n) (each node visited once)
• Space: O(n) (call stack depth)

Why This Works

• Recursion decomposes the problem into smaller subproblems.
• The call stack ensures we process nodes in reverse order.

Example 3 – Hard (Reverse Sublist)

Problem: Reverse a linked list from position m to n (1-indexed). Input: 1 -> 2 -> 3 -> 4 -> 5 -> None, m = 2, n = 4 Output: 1 -> 4 -> 3 -> 2 -> 5 -> None

Thought Process

1. Use a dummy node to handle edge cases (e.g., reversing from the head).
2. Traverse to the (m-1)th node (prev).
3. Reverse the sublist from m to n iteratively:
4. Initialize curr = prev.next (start of sublist).
5. Reverse n - m + 1 nodes.
6. Reconnect the reversed sublist to the original list.

Code (Python)

def reverseBetween(head: ListNode, m: int, n: int) -> ListNode:

    dummy = ListNode(0, head)

    prev = dummy


    # Move prev to (m-1)th node

    for _ in range(m - 1):

        prev = prev.next


    # Reverse sublist

    curr = prev.next

    for _ in range(n - m):

        next_node = curr.next

        curr.next = next_node.next

        next_node.next = prev.next

        prev.next = next_node


    return dummy.next

Complexity

• Time: O(n) (single pass)
• Space: O(1) (constant extra space)

Why This Works

• We isolate the sublist and reverse it in-place while maintaining connections to the rest of the list.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. To reverse a linked list: 1. Iterative: Use prev, curr, and next to flip links in one pass. Time: O(n), Space: O(1). 2. Recursive: Base case is head or head.next is None. Reverse the rest, then fix the current node’s link. Time: O(n), Space: O(n). 3. Sublist: Use a dummy node, traverse to m-1, reverse n-m+1 nodes, and reconnect. Common pitfalls? Losing next, cycles, and off-by-one errors. Practice the edge cases—empty list, single node, and full reversal. You’ve got this!

? Final Tips for Interviews

• Draw it out: Sketch the list before and after reversal.
• Test edge cases: Empty list, single node, two nodes.
• Explain trade-offs: Iterative (space-efficient) vs. recursive (elegant but stack-heavy).
• Time yourself: Aim for < 10 minutes for the basic problem.

Now go ace that interview! ?