Reverse Linked List

Approach Summary

Iterative: maintain prev and curr. At each step, save next, point curr.next to prev, advance both. Recursive: reverse rest, link back.

Full Solution & Approach

Reversing a singly linked list means every node's next pointer must point at its predecessor. The iterative trick is to walk the list once while rewriting links on the fly using three pointers: prev (the already-processed part), cur (the current node), and next (the saved remainder). For each node, save cur.next before overwriting it, point cur.next at prev, then advance prev to cur and cur to the saved next. When cur becomes null the whole list has been reversed and prev is the new head. This is O(n) time and O(1) space and is the version interviewers most often expect. The recursive alternative returns the new head from the base case (null or a single node) and rewires node.next.next = node after the recursive call, but costs O(n) stack space.

Exactly one pass over the n nodes — O(n) time. Three pointers regardless of list length — O(1) extra space for the iterative version.

Solution Code

Solution

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

function reverseList(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

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

Edge Cases to Watch

Empty list — prev is null, returns null
Single node — the loop never runs, returns the node
List with a cycle — would loop forever; the problem assumes an acyclic list

How to Recognize This Pattern

Reverse linked list in-place

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)