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 changing where the nodes point.

The existing nodes are sufficient. The algorithm changes their next pointers and keeps references to the previous, current, and next nodes.

Understanding the Problem

Given the head of a singly linked list, reverse it and return the new head. The solution must use O(1) extra space. It must not allocate replacement nodes or a data structure that grows with the list.

My First Approach

My initial solution collects all values into an array, then prepends each value to a new list. The values must be read in their original order for this to reverse the list. Supply a ListNode(value, next) constructor to run this version outside the problem platform.

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 = 0; i < values.length; i++) {
    newHead = new ListNode(values[i], newHead);
  }

  return newHead;
}

This version needs O(n) extra space for the array and creates new nodes. Reversing the existing links removes both allocations.

The In Place Approach

I keep three references so that each pointer change preserves access to the remaining nodes:

• prev: The previous node (so we can point current to it)
• current: The node we are currently processing
• next: The next node (so we do not 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.

In place reversal

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;
}

Pointer updates

For 1 → 2 → 3 → 4 → null, the pointers move as follows:

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:

1. Save the next node: Once we reverse the link, we lose access to the rest of the list
2. Reverse the current link: Point current.next to prev
3. Move both pointers forward: prev becomes current, current becomes next
4. Repeat: Continue until the current node is null

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:

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

Reversal summary

• In place manipulation uses O(1) extra space
• Track prev, current, and next, saving next before reversing a link
• The pattern of tracking multiple pointers applies to many linked list problems

Learning in place manipulation changed how I think about linked lists. I now look for ways to rearrange existing nodes before creating new structures. The technique is useful in other linked list problems.