Reverse Linked List

Reverse a singly linked list.

Function signature

func ReverseList(head *ListNode) *ListNode

Inputs / outputs

• head: head of the list.
• Return: new head of the reversed list.

Example

1 -> 2 -> 3 -> nil
Output: 3 -> 2 -> 1 -> nil

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

Iteratively reverse pointers with prev, curr, next.

Invariant: prev is the reversed list so far; curr is the remaining list.

Algorithm (step-by-step)

1. Initialize prev = nil, curr = head.
2. While curr != nil:
   • Save next = curr.Next.
   • Point curr.Next to prev.
   • Move prev to curr, curr to next.
3. Return prev.

Correctness sketch

• Invariant: prev is the reversed list so far; curr is the remaining list.
• Pointer rewiring preserves all nodes and changes only their order or links.
• Each step maintains list connectivity and the intended invariant.
• When the traversal ends, the list structure matches the required transformation.

Trace (hand walkthrough)

Example input:
1 -> 2 -> 3 -> nil
Output: 3 -> 2 -> 1 -> nil

Walk:
- prev=nil, curr=1 -> 1->nil
- curr=2 -> 2->1->nil
- curr=3 -> 3->2->1->nil

Pitfalls to avoid

• Losing the next pointer before rewiring.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Store next := cur.Next before rewiring.
• Update cur.Next = prev, then advance prev, cur.