Reversing a Linked List

1. Introduction: The Ultimate Pointer Test

If there is one algorithmic problem you MUST memorize before any coding interview, it is Reverse a Linked List. It is the "FizzBuzz" of data structures.

Reversing a Linked List requires absolute mastery over pointers. You are physically changing the direction of the next arrows. If you change a pointer too early, you lose the rest of the list forever. If you don't update your previous pointer correctly, you create a cycle.

Reversing is not just a standalone problem; it is a fundamental sub-routine used to solve complex problems like checking if a list is a palindrome, or folding a list in half.

2. Core Concept: The 3-Pointer Juggle

To reverse a list iteratively, you need exactly three pointers:

1. prev: Starts as null. This will become the new target for the next arrows.
2. curr: Starts as head. The node we are currently rewiring.
3. nextTemp: A temporary variable created inside the loop. It holds the original next node so we don't lose the rest of the list when we overwrite curr.next.

The Dance:

1. Save the next node: nextTemp = curr.next
2. Reverse the arrow: curr.next = prev
3. Shift prev forward: prev = curr
4. Shift curr forward: curr = nextTemp

3. Beginner Code Example: Reverse Linked List (Iterative)

Problem Statement: (LeetCode 206) Given the head of a singly linked list, reverse the list, and return the reversed list.

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class ReverseList {
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            // 1. Save the rest of the list
            ListNode nextTemp = curr.next;
            
            // 2. Reverse the pointer
            curr.next = prev;
            
            // 3. Move pointers forward one step
            prev = curr;
            curr = nextTemp;
        }
        
        // When the loop ends, curr is null, and prev is the new head!
        return prev;
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We visit every node once.
• Space Complexity: $O(1)$. We only use a few pointers.

4. Intermediate Code Example: Reverse Linked List (Recursive)

Interviewers love asking for the recursive solution to test your understanding of the call stack.

The Insight: If the list is 1 -> 2 -> 3 -> 4, assume the recursive call magically reverses the rest of the list starting from 2. So we have 1 -> 2 <- 3 <- 4. How do we fix the connection between 1 and 2? We want 2 to point to 1. 2 is currently head.next. So we say head.next.next = head. Then we break 1's forward pointer: head.next = null.

public class ReverseListRecursive {
    public static ListNode reverseList(ListNode head) {
        // Base case: empty list or last node
        if (head == null || head.next == null) {
            return head; 
        }
        
        // Recurse all the way to the end. p is the new head of the reversed list!
        ListNode p = reverseList(head.next);
        
        // Rewire the pointers as the call stack unwinds
        head.next.next = head; // Make the next node point back to us
        head.next = null;      // Cut our forward pointer to prevent cycles
        
        return p; // Keep passing the new head back up the chain
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$.
• Space Complexity: $O(N)$ due to the recursive call stack. (This makes it inferior to the iterative approach for production code).

5. Advanced Code Example: Reverse Nodes in k-Group

Problem Statement: (LeetCode 25) Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

The Insight: This requires a Dummy node, and extreme pointer management. We must count k nodes. If we have k, we reverse just that sub-segment. We must carefully reconnect the tail of the newly reversed sub-segment to the rest of the list, and update our prev pointer for the next group.

public class ReverseKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode prevGroupTail = dummy;
        ListNode curr = head;
        
        while (curr != null) {
            // 1. Check if we have k nodes left
            ListNode groupEnd = curr;
            int count = 0;
            while (groupEnd != null && count < k - 1) {
                groupEnd = groupEnd.next;
                count++;
            }
            
            // If we don't have k nodes, we are done!
            if (groupEnd == null) break;
            
            // 2. Save the start of the next group
            ListNode nextGroupHead = groupEnd.next;
            
            // 3. Sever the list to reverse just this segment
            groupEnd.next = null;
            
            // 4. Reverse the k-group
            ListNode reversedHead = ReverseList.reverseList(curr);
            
            // 5. Reconnect to the main list
            // curr is now the TAIL of this reversed group!
            prevGroupTail.next = reversedHead;
            curr.next = nextGroupHead;
            
            // 6. Setup for the next iteration
            prevGroupTail = curr;
            curr = nextGroupHead;
        }
        
        return dummy.next;
    }
}

6. Common Mistakes Beginners Make

1. Returning curr instead of prev

   • The Mistake: return curr; at the end of iterative reversal.
   • Why it's wrong: The while (curr != null) loop specifically terminates when curr falls off the end of the list and becomes null. Returning null means your function erases the entire list! The prev pointer is holding the last actual node, which is the new head.

2. Creating Cycles during Sub-Reversals

   • The Mistake: Reversing a sub-segment (like in Reverse Linked List II) and forgetting to set the tail's next to null before reversing, or forgetting to link it to the rest of the list afterwards.
   • Why it's wrong: The old pointers still exist. If you don't explicitly sever and reconnect, traversing the list will trap you in an infinite loop.

3. Losing the rest of the list

   • The Mistake: Writing curr.next = prev; curr = curr.next;.
   • Why it's wrong: You overwrote curr.next on line 1! Moving curr to curr.next just moves it to prev, effectively walking backwards forever. You MUST save the original next in a temporary variable first.

7. Interview Q&A

Q1: How do you check if a Linked List is a Palindrome in $O(1)$ space? (LeetCode 234) Answer: Use Fast/Slow pointers to find the middle. Reverse the second half of the list in place! Then use two pointers, one at the head and one at the new middle, and compare values. Finally (optional but polite), reverse the second half back to restore the original list structure.

Q2: What is "Reverse Linked List II"? (LeetCode 92) Answer: You are given left and right indices and must reverse only that portion. You traverse to the left node, save the node just before it, reverse exactly right - left + 1 nodes using the standard 3-pointer trick, and then stitch the saved nodes back together.

Q3: Can you reverse a Doubly Linked List the same way? Answer: Yes, but it's even easier. You just traverse the list, and for every single node, you swap its prev and next pointers. You don't need a temporary variable for the rest of the list because the prev pointer holds it for you!

8. Practice Problems

1. Reverse Linked List (LeetCode 206)
   • Goal: Write both Iterative and Recursive versions flawlessly from memory.
2. Reverse Linked List II (LeetCode 92)
   • Goal: Master sub-segment reversal without breaking the list.
3. Palindrome Linked List (LeetCode 234)
   • Hint: Combine Fast/Slow pointers with in-place Reversal.

9. Summary

• The Iterative Formula: nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp;. Memorize this!
• Return Value: Always return prev.
• Recursion: Requires manipulating head.next.next = head on the way back up the call stack. Beautiful but consumes $O(N)$ memory.
• K-Groups: Use a Dummy node, count $K$ nodes, sever the list, reverse, and stitch it back.