# Reverse Linked List

- **Canonical ID**: `reverse-linked-list`
- **Canonical URL**: https://dsacheatsheet.com/problems/reverse-linked-list
- **Difficulty**: easy
- **Patterns**: Linked Lists
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/reverse-linked-list/

## 1. Core Invariant / The Trick

Maintain `prev = None` and `curr = head`. Before reversing `curr.next = prev`, save `nxt = curr.next`, then advance `prev, curr = curr, nxt`. Return `prev`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Visits each node once redirecting one pointer with constant auxiliary variables.

## 3. Minimal Idiomatic Code

### Python
```python
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev
```

### TypeScript
```typescript
export function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;
  while (curr !== null) {
    const nxt = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nxt;
  }
  return prev;
}
```

### C++
```cpp
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr) {
        ListNode* nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}
```

### Java
```java
ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}
```

### Go
```go
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        nxt := curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    }
    return prev
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Dropping `nxt` before mutating `curr.next` loses the rest of the list.
- Returning `head` instead of `prev` yields only the old head node with `next = null`.

### Follow-ups
- Recursive version uses O(N) call stack space; Reverse Linked List II reverses a slice `[left, right]` with a dummy node.