In-Place Reversal of a Linked List

1. Introduction

Reversing a linked list in-place is a core data structure operation and a fundamental coding pattern.
The goal is simple:

Given a linked list, reverse the order of nodes without using extra memory.

For example:

Original list:

1 → 2 → 3 → 4 → 5 → null

After in-place reversal:

5 → 4 → 3 → 2 → 1 → null

This operation is widely used in real-world applications and algorithmic problems:

Undo/redo operations in editors
Reversing a sequence of operations or tasks
Adding numbers stored in linked lists
Palindrome detection
Reversing segments in advanced linked list manipulations

The key insight is to manipulate the next pointers of the nodes directly, rather than creating a new list.

2. Problem Definition

Input: Head of a singly linked list.

Output: Head of the reversed linked list.

Constraints:

Must reverse in-place (O(1) extra space)
Time complexity should ideally be O(n)

3. Conceptual Understanding

A singly linked list is made up of nodes, where each node has:

value (data)
next pointer (points to the next node or null)

Reversing it in-place requires changing the direction of each node’s next pointer, so it points to the previous node instead of the next node.

Visual Example:

Original: 1 → 2 → 3 → 4 → 5 → null
Reversed: 5 → 4 → 3 → 2 → 1 → null

We maintain three pointers during iteration:

prev → Initially null (will become the new tail)
current → Initially head
next → Temporarily stores current.next so we don’t lose track of the remaining nodes

4. Step-by-Step Iterative Approach

Initial setup:

prev = null
current = head → 1

Iteration 1:

Store next = current.next → 2
Reverse pointer: current.next = prev → null
Move pointers: prev = current → 1, current = next → 2

List now:

1 → null    2 → 3 → 4 → 5

Iteration 2:

Store next = current.next → 3
Reverse pointer: current.next = prev → 1
Move pointers: prev = current → 2, current = next → 3

List now:

2 → 1 → null    3 → 4 → 5

Iteration 3:

Store next = current.next → 4
Reverse pointer: current.next = prev → 2
Move pointers: prev = current → 3, current = next → 4

List now:

3 → 2 → 1 → null    4 → 5

Iteration 4:

Store next = current.next → 5
Reverse pointer: current.next = prev → 3
Move pointers: prev = current → 4, current = next → 5

List now:

4 → 3 → 2 → 1 → null    5

Iteration 5:

Store next = current.next → null
Reverse pointer: current.next = prev → 4
Move pointers: prev = current → 5, current = next → null

List now:

5 → 4 → 3 → 2 → 1 → null

Done! prev points to the new head.

5. Java Implementation – Iterative

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class ReverseLinkedList {

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;

        while (current != null) {
            ListNode nextNode = current.next; // store next node
            current.next = prev;              // reverse current node's pointer
            prev = current;                   // move prev forward
            current = nextNode;               // move current forward
        }

        return prev; // new head of the reversed list
    }
}

Time Complexity: O(n) – Each node is visited once
Space Complexity: O(1) – In-place reversal, no extra data structures

6. Recursive Approach

The recursive approach uses the call stack to reverse links:

Concept:

Recursively reverse the sublist starting from the second node
Attach the first node at the end of the reversed sublist

Java Implementation:

public ListNode reverseListRecursive(ListNode head) {
    // Base case: empty or single node
    if (head == null || head.next == null) return head;

    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head; // reverse the link
    head.next = null;      // prevent cycle

    return newHead;
}

Time Complexity: O(n)
Space Complexity: O(n) due to recursion stack

Note: Iterative approach is preferred for large lists to avoid stack overflow.

7. Edge Cases

Empty list: head = null → return null
Single node list: return the same node
Two-node list: simple swap works
Already reversed list: algorithm still works correctly
Large lists: use iterative to avoid recursion stack overflow

8. Variants of Reversal Problems

Reverse first k nodes – Reverse a fixed-length prefix of the list.
Reverse in groups of k nodes – Advanced problem used in competitive programming.
Reverse between positions m and n – Reverse a sublist within a given range.
Reverse doubly linked list – Adjust both next and prev pointers.
Check palindrome linked list – Reverse half of the list to compare halves.
Add two numbers stored in linked lists – Reversing helps in processing digits from least significant to most significant.

9. Real-World Applications

Undo/Redo operations – Reverse action history stored in linked lists.
Reversing sequences – e.g., memory blocks or tasks in order.
Algorithms – Palindrome check, addition of numbers, k-group reversals.
Stacks – Implement stack operations in reverse order efficiently.

10. Stepwise Tips for Understanding

Always maintain three pointers: prev, current, next.
Save the next node first to avoid losing the rest of the list.
Reverse the current node’s pointer before moving forward.
Move prev and current pointers forward after reversal.
At the end of iteration, prev points to the new head.

11. Complexity Analysis

Method	Time Complexity	Space Complexity
Iterative	O(n)	O(1)
Recursive	O(n)	O(n) stack

Why Iterative is preferred: Constant space usage and avoids stack overflow in large linked lists.

12. Common Mistakes

Not storing next before changing current.next → breaks the list
Forgetting to set head.next = null in recursive approach → cycle
Using recursion for very large lists → stack overflow
Confusing prev and current updates

13. Summary

Step	Action
1	Initialize `prev = null`, `current = head`
2	Loop while `current != null`
3	Store `next = current.next`
4	Reverse pointer: `current.next = prev`
5	Move `prev = current`, `current = next`
6	After loop, `prev` is the new head

Key Points:

Iterative approach is O(n) time, O(1) space
Recursive approach is elegant but uses O(n) stack space
Understanding pointer manipulation is crucial for all linked list problems