Leetcode - Reverse Linked List Solution

Reversing a linked list is a fundamental skill that comes up in many coding interviews. My first solution created a new list, which worked but used O(n) extra memory. Then I learned the in-place technique that uses O(1) space by simply changing where the nodes point. It's more elegant and efficient.

The key insight is that we don't need to create new nodes. We can reverse the list by changing the next pointers of existing nodes. This requires tracking three pointers: previous, current, and next.

Understanding the Problem

Given the head of a singly linked list, reverse it and return the new head. The challenge is doing this in-place with O(1) extra space, meaning we can't create new nodes or use additional data structures proportional to the list size.

My First Approach

My initial solution collected all values into an array, then built a new list in reverse order.

function reverseLinkedListNaive(head) {
  const values = [];
  let current = head;

  // Collect values
  while (current) {
    values.push(current.val);
    current = current.next;
  }

  // Build new list in reverse
  let newHead = null;
  for (let i = values.length - 1; i >= 0; i--) {
    newHead = new ListNode(values[i], newHead);
  }

  return newHead;
}

This works, but it uses O(n) extra space for the array and creates new nodes. For large lists, this isn't ideal. I wanted to do better.

The In-Place Approach

The key insight: we don't need new nodes! We can just change where existing nodes point. To do this safely, we need to track three things:

prev: The previous node (so we can point current to it)
current: The node we're currently processing
next: The next node (so we don't lose the rest of the list)

The algorithm works by iterating through the list, reversing each link as we go. We save the next node before reversing the link, then move all three pointers forward.

The Solution

function reverseLinkedList(head) {
  let prev = null; // Previous node (starts as null - new tail)
  let current = head; // Current node we're processing

  while (current !== null) {
    // Save next node before we lose it
    let next = current.next;

    // Reverse the link: point current to previous
    current.next = prev;

    // Move both pointers forward
    prev = current;
    current = next;
  }

  // prev is now the new head
  return prev;
}

How It Works

Let me trace through reversing 1 → 2 → 3 → 4 → null:

Initial state: 1 → 2 → 3 → 4 → null

prev = null, current = 1

Step 1:

Save next = 2
Reverse link: 1 → null
Move: prev = 1, current = 2
State: null ← 1 2 → 3 → 4 → null

Step 2:

Save next = 3
Reverse link: 2 → 1
Move: prev = 2, current = 3
State: null ← 1 ← 2 3 → 4 → null

Step 3:

Save next = 4
Reverse link: 3 → 2
Move: prev = 3, current = 4
State: null ← 1 ← 2 ← 3 4 → null

Step 4:

Save next = null
Reverse link: 4 → 3
Move: prev = 4, current = null
State: null ← 1 ← 2 ← 3 ← 4

Result: 4 → 3 → 2 → 1 → null

Why This Works

The algorithm works by systematically reversing each link:

Save the next node - This is crucial because once we reverse the link, we lose access to the rest of the list
Reverse the current link - Point current.next to prev
Move both pointers forward - prev becomes current, current becomes next
Repeat - Continue until we've processed all nodes

When the loop ends, prev points to what was the last node, which is now the new head.

Complexity Analysis

Time Complexity: O(n)

We visit each node exactly once
Each operation (saving next, reversing link, moving pointers) is O(1)

Space Complexity: O(1)

Only using three pointer variables (prev, current, next)
No additional data structures
No new nodes created

Common Pitfalls

When implementing this, watch out for:

Losing the rest of the list: Always save next before reversing the link
Returning the wrong node: Remember that prev is the new head after the loop
Edge cases: Handle empty lists (head === null) and single-node lists
Null pointer errors: Make sure to check current !== null in the loop condition

Key Takeaways

In-place manipulation means O(1) extra space
Track prev, current, and next to navigate safely
Changing pointers is often enough - no new nodes needed
This is a fundamental linked list manipulation technique
The pattern of tracking multiple pointers appears in many linked list problems

Learning in-place manipulation changed how I think about linked lists. Instead of creating new structures, I now think about rearranging what's already there. It's more elegant, efficient, and often exactly what interviewers are looking for. This technique forms the foundation for many other linked list problems.