#18 · Linked List

Reverse Linked List

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

EasyLeetCode

Current node
Link just rewired
Done / in result
Marked
Rejected
Dummy head

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Singly linked list

A chain of nodes, each holding a value and a next reference. Only the head is known; every other node is reached by following next. Insertion or removal after a known node is O(1), but reaching the i-th node costs O(i).

Memory layout

Nodes are separate heap objects scattered in memory, linked by pointers. There is no contiguous block, so traversal chases pointers (poor cache locality) and each node pays pointer overhead on top of its value.

Operation	Cost
access i-th node	O(i)
insert / remove after a known node	O(1)
reverse whole list	O(n) time, O(1) space (in place)

Pointer rewiring (prev / curr / next)

Reversal changes direction of each link. Because a singly linked node cannot look back, we carry the previous node with us, and save the next node before overwriting the link that leads to it.

Memory layout

Three local references on the stack; the nodes themselves never move.

Operation	Cost
flip one link	O(1)

Why it fits

A link can be redirected in O(1) without touching any other node, so the list can be reversed in place with a single pass.
The only information lost when flipping curr.next is where the rest of the list is, so saving it first (next) is the one trick that matters.
Reversal is the building block for harder problems (reorder list, palindrome list, reverse in groups), so the technique has to be second nature.

Why alternatives degrade

Copy values to an array and write them back:: Needs O(n) extra memory and a second pass, and it moves the data rather than the nodes, which is wrong when nodes carry identity or large payloads.
Recursion:: Correct and elegant, but uses O(n) call-stack frames, which overflows the stack for long lists (100k+ nodes).
Doubly linked list:: Reversal would be just a swap of prev and next per node, but it costs an extra pointer per node and does not apply to the singly linked input given.

Four approaches, from naive to production

1 · beginner

Copy values out and write them back

time O(n)space O(n)

Walk the list once to collect the values in an array, reverse the array, then walk the list again overwriting each node's value.

ListNode* reverseList(ListNode* head) {
    vector<int> vals;
    for (ListNode* node = head; node; node = node->next) vals.push_back(node->val);
    reverse(vals.begin(), vals.end());
    int i = 0;
    for (ListNode* node = head; node; node = node->next) node->val = vals[i++];
    return head;
}

public ListNode reverseList(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode node = head; node != null; node = node.next) vals.add(node.val);
    Collections.reverse(vals);
    int i = 0;
    for (ListNode node = head; node != null; node = node.next) node.val = vals.get(i++);
    return head;
}

def reverse_list(head):
    vals = []
    node = head
    while node:
        vals.append(node.val)
        node = node.next
    vals.reverse()
    node, i = head, 0
    while node:
        node.val = vals[i]
        i += 1
        node = node.next
    return head

function reverseList(head: ListNode | null): ListNode | null {
  const vals: number[] = [];
  for (let node = head; node; node = node.next) vals.push(node.val);
  vals.reverse();
  for (let node = head, i = 0; node; node = node.next) node.val = vals[i++];
  return head;
}

Flaws & bottlenecks

Needs an O(n) array and two full passes.
It never re-links anything: nodes keep their identity but swap contents, which is wrong if other references point at specific nodes or the value is large.
Does not generalize to reversing part of a list without extra bookkeeping.

Interviewer cross-questions

Is this really reversing the linked list?

Say: Not really. The structure stays identical and only the stored numbers are permuted. If another part of the program holds a pointer to the node that used to be first, it now sees a different value. Real reversal changes the links.

Can you do it without extra space?

Say: Yes: re-link the nodes in place. Walk the list once, redirecting each node's next arrow to the node before it (iterative prev/curr/next).

What if the values are large objects?

Say: Copying them twice is expensive. Moving pointers instead of payloads costs O(1) per node regardless of node size.

2 · intermediate

Recursion

time O(n)space O(n)

Reverse everything after head recursively, then make the node after head point back at head and cut head's old forward link.

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

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

def reverse_list(head):
    if not head or not head.next:
        return head
    new_head = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return new_head

function reverseList(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

Flaws & bottlenecks

Call stack depth equals the list length: a few tens of thousands of nodes overflow the stack in most runtimes.
The pointer surgery happens on the way back up, which makes the order of operations harder to follow than a loop.
The temporary 2-cycle (head ⇄ head.next) before `head.next = null` is easy to forget to cut, creating a cycle.

Interviewer cross-questions

What is the space complexity?

Say: O(n): one stack frame per node because the recursion goes all the way to the last node before any pointer is changed. Only the iterative version is O(1).

Why must head.next be set to none?

Say: After head.next.next = head, the two nodes point at each other. Without cutting head.next the old head would still point forward, leaving a cycle (and an infinite loop when printing the list).

How do you convert it to a loop?

Say: Keep the "reversed so far" list in a prev variable and process nodes front to back, saving next before flipping the arrow. That is exactly the iterative solution.

3 · advanced

Iterative prev / curr / next

time O(n)space O(1)

Walk the list once. For each node, remember its next node, point it back at prev, then advance prev and curr. The new head is the last prev.

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

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

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

Flaws & bottlenecks

Mutates the input list, so the original order is lost unless it is copied first.
Forgetting to save next before redirecting curr.next orphans the rest of the list.
No protection against a cyclic input: it would reverse forever or corrupt the cycle.

Interviewer cross-questions

Why do you need the next variable?

Say: Once curr.next = prev runs, the only link to the rest of the list is gone. Saving next first keeps it reachable.

What are the edge cases?

Say: Empty list (returns none), one node (loop runs once and returns that node), and two nodes (the smallest case where the order really changes).

How would you reverse only a sub-range?

Say: Walk to the node before the range, then apply the same flip (or the head-insertion form) for just the required number of nodes and re-attach both ends.

4 · expert

Head insertion behind a dummy node

time O(n)space O(1)

Keep tail on the first node. Repeatedly unhook tail.next and insert it right after a dummy head. Each node is moved exactly once and the list is always valid between iterations.

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode dummy(0, head);
    ListNode* tail = head;
    while (tail->next) {
        ListNode* moved = tail->next;
        tail->next = moved->next;
        moved->next = dummy.next;
        dummy.next = moved;
    }
    return dummy.next;
}

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode dummy = new ListNode(0, head);
    ListNode tail = head;
    while (tail.next != null) {
        ListNode moved = tail.next;
        tail.next = moved.next;
        moved.next = dummy.next;
        dummy.next = moved;
    }
    return dummy.next;
}

def reverse_list(head):
    if not head or not head.next:
        return head
    dummy = ListNode(0, head)
    tail = head
    while tail.next:
        moved = tail.next
        tail.next = moved.next
        moved.next = dummy.next
        dummy.next = moved
    return dummy.next

function reverseList(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  const dummy = new ListNode(0, head);
  const tail = head;
  while (tail.next) {
    const moved = tail.next;
    tail.next = moved.next;
    moved.next = dummy.next;
    dummy.next = moved;
  }
  return dummy.next;
}

Flaws & bottlenecks

Does three pointer writes per node (against two for prev/curr/next), a small constant-factor cost.
Allocates a dummy node (negligible, and avoidable in languages with stack allocation).
Less well known than prev/curr/next, so reviewers may need the invariant explained.

Interviewer cross-questions

Why is this preferred for sub-range reversal?

Say: The list is a valid, fully linked list after every iteration, and tail already sits where the range ends. To reverse positions m..n you start the dummy at the node before m and run the loop n−m times, with no extra re-attachment code.

What invariant does the loop keep?

Say: dummy.next .. tail is the reversed prefix, and tail.next .. end is the untouched suffix. Each iteration moves one node from the suffix to the front of the prefix.

How would you make it safe for concurrent readers?

Say: It is not: readers can see intermediate states. For lock-free readers you would build the reversed list as a new chain (O(n) allocation) and swap the head pointer atomically.

Synchronized code walkthrough

Showing: Copy values out and write them back — shares the player above; click any step to jump.

ListNode* reverseList(ListNode* head) {
    vector<int> vals;
    for (ListNode* node = head; node; node = node->next) vals.push_back(node->val);
    reverse(vals.begin(), vals.end());
    int i = 0;
    for (ListNode* node = head; node; node = node->next) node->val = vals[i++];
    return head;
}

public ListNode reverseList(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode node = head; node != null; node = node.next) vals.add(node.val);
    Collections.reverse(vals);
    int i = 0;
    for (ListNode node = head; node != null; node = node.next) node.val = vals.get(i++);
    return head;
}

def reverse_list(head):
    vals = []
    node = head
    while node:
        vals.append(node.val)
        node = node.next
    vals.reverse()
    node, i = head, 0
    while node:
        node.val = vals[i]
        i += 1
        node = node.next
    return head

function reverseList(head: ListNode | null): ListNode | null {
  const vals: number[] = [];
  for (let node = head; node; node = node.next) vals.push(node.val);
  vals.reverse();
  for (let node = head, i = 0; node; node = node.next) node.val = vals[i++];
  return head;
}

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

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

def reverse_list(head):
    if not head or not head.next:
        return head
    new_head = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return new_head

function reverseList(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

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

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode dummy(0, head);
    ListNode* tail = head;
    while (tail->next) {
        ListNode* moved = tail->next;
        tail->next = moved->next;
        moved->next = dummy.next;
        dummy.next = moved;
    }
    return dummy.next;
}

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode dummy = new ListNode(0, head);
    ListNode tail = head;
    while (tail.next != null) {
        ListNode moved = tail.next;
        tail.next = moved.next;
        moved.next = dummy.next;
        dummy.next = moved;
    }
    return dummy.next;
}

def reverse_list(head):
    if not head or not head.next:
        return head
    dummy = ListNode(0, head)
    tail = head
    while tail.next:
        moved = tail.next
        tail.next = moved.next
        moved.next = dummy.next
        dummy.next = moved
    return dummy.next

function reverseList(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;
  const dummy = new ListNode(0, head);
  const tail = head;
  while (tail.next) {
    const moved = tail.next;
    tail.next = moved.next;
    moved.next = dummy.next;
    dummy.next = moved;
  }
  return dummy.next;
}