Dev Cookies

Posted on Apr 12

🔁 Linked List In-Place Reversal in Java – A Step-by-Step Guide

In-place reversal of a linked list is a classic and frequently asked interview question. It tests your understanding of pointer manipulation, linked list traversal, and writing clean, space-efficient code.

🧠 What Does “In-Place” Mean?

"In-place" means you reverse the list using constant space – without using an extra array, stack, or recursion.

No extra data structure – just pointer changes! ⚙️

📘 Problem Statement

Given the head of a singly linked list, reverse the list in-place and return the new head.

🔄 Example

Input:

1 → 2 → 3 → 4 → 5 → null

Output:

5 → 4 → 3 → 2 → 1 → null

🧩 Intuition

To reverse the list:

Start with prev = null
Traverse the list with a pointer curr
For every node:
- Temporarily store curr.next
- Point curr.next to prev (reverse the link)
- Move prev to curr
- Move curr to next

Repeat until curr is null.

🧑‍💻 Java Code

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

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

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

    return prev;  // new head of reversed list
}

🎯 Dry Run

Let’s reverse 1 → 2 → 3 → null step-by-step:

Initially:
prev = null
curr = 1

Step 1:
next = 2
1.next = null
prev = 1
curr = 2

Step 2:
next = 3
2.next = 1
prev = 2
curr = 3

Step 3:
next = null
3.next = 2
prev = 3
curr = null

Final result: 3 → 2 → 1 → null

📊 Time & Space Complexity

Metric	Value
Time	O(n)
Space	O(1)

✅ One-pass linear time

✅ Constant auxiliary space

🧪 Test Cases

// Case 1: Normal list
Input: 1 → 2 → 3
Output: 3 → 2 → 1

// Case 2: One node
Input: 1
Output: 1

// Case 3: Empty list
Input: null
Output: null

🧠 Follow-up Interview Questions

Can you reverse only part of the list?

(e.g., positions m to n)
Can you reverse in k-groups?

(LeetCode 25: Reverse Nodes in k-Group)
Can you reverse a doubly linked list?
What if it’s a circular linked list?

🧩 Variations & LeetCode Problems

Problem	Description
Reverse Linked List – LeetCode 206	Reverse entire list
Reverse Linked List II – LeetCode 92	Reverse sublist from position `m` to `n`
Reverse Nodes in k-Group – LeetCode 25	Reverse every `k` nodes
Palindrome Linked List – LeetCode 234	Use in-place reverse to check palindrome

📦 Bonus: Recursive Version

public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

📌 Less memory efficient due to call stack.

🏁 Conclusion

Reversing a linked list in-place is a must-know technique for interviews and real-world software. It teaches you pointer manipulation, loop control, and elegant problem-solving with space constraints.

Master this and you’ll have a solid foundation for advanced linked list problems. 🚀

DEV Community