Reverse Linked List

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

Example

Input: 1 2 3 4 5 Output: 5 4 3 2 1

Approach

Walk the list once, rewiring each node's next pointer to point backward to the previous node instead of forward. The classic trap: you must save a reference to the next node before overwriting current.next, or you lose the rest of the list permanently.

Walkthrough

1prev, curr = None, head
2while curr:
3    nxt = curr.next
4    curr.next = prev
5    prev = curr
6    curr = nxt
7return prev

Input format

Line 1: the list values, space-separated

Print the reversed list, space-separated.