Reverse Linked List

If there's one Linked List pattern that every developer should master, it's reversing a Linked List.

This problem teaches pointer manipulation, which later helps in solving problems like:

• Reverse Nodes in K Group
• Palindrome Linked List
• Reorder List
• Reverse Between Positions

Let's understand the intuition behind it.

---

Problem Statement

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

Example

Input:
1 -> 2 -> 3 -> 4 -> 5

Output:
5 -> 4 -> 3 -> 2 -> 1

---

Brute Force Approach

Intuition

A straightforward approach is to store all node values inside an ArrayList.

Then traverse the linked list again and replace node values from the array in reverse order.

Although it works, we're using extra space just to remember previous elements.

Complexity

Time Complexity  : O(N)
Space Complexity : O(N)

Brute Force Code

class Solution {
    public ListNode reverseList(ListNode head) {

        ArrayList<Integer> values = new ArrayList<>();

        ListNode temp = head;

        while (temp != null) {
            values.add(temp.val);
            temp = temp.next;
        }

        temp = head;
        int index = values.size() - 1;

        while (temp != null) {
            temp.val = values.get(index--);
            temp = temp.next;
        }

        return head;
    }
}

---

Moving Towards the Optimal Approach

Instead of storing values separately, can we reverse the actual links between nodes?

Since Linked Lists are made of pointers, reversing those pointers directly would save extra space.

This leads us to the optimal solution.

---

Optimal Approach - Three Pointer Technique

We'll maintain three pointers:

prev
curr
next

For every node:

1. Store the next node.
2. Reverse the current node's pointer.
3. Move all pointers one step ahead.

---

Visual Intuition

Initially:

null <- 1 -> 2 -> 3 -> 4 -> 5
       ^
      curr

After first reversal:

null <- 1    2 -> 3 -> 4 -> 5
       ^
      prev
            ^
           curr

Continue the same process until the list ends.

---

Dry Run

Input

1 -> 2 -> 3 -> null

Initial State

prev = null
curr = 1

Iteration 1

next = 2

1 -> null

prev = 1
curr = 2

Iteration 2

next = 3

2 -> 1 -> null

prev = 2
curr = 3

Iteration 3

next = null

3 -> 2 -> 1 -> null

prev = 3
curr = null

Loop ends.

Return:

prev

which is now the new head.

---

Optimal Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */

class Solution {
    public ListNode reverseList(ListNode head) {

        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {

            ListNode next = curr.next;

            curr.next = prev;

            prev = curr;
            curr = next;
        }

        return prev;
    }
}

---

Why This Works

The key line is:

curr.next = prev;

which reverses one link at a time.

Before breaking the original link, we safely store:

ListNode next = curr.next;

so we never lose access to the remaining list.

By the time we reach the end, every pointer has been reversed.

---

Complexity Analysis

Time Complexity  : O(N)
Space Complexity : O(1)

• Every node is visited exactly once.
• No extra data structure is used.

---

Key Takeaway

Whenever you encounter a Linked List reversal problem, immediately think about the prev → curr → next pattern.

Mastering this single technique unlocks a huge portion of Linked List interview questions.

---