Reverse Linked List
Easy· pointer manipulation
Problem
Given the head of a singly linked list, reverse the direction of every link and return the new head. Try both an iterative and a recursive version.
Examples
Input: head = [5,4,3,2,1]
Output: [1,2,3,4,5]
Input: head = [7,9]
Output: [9,7]
Constraints
- • 0 <= number of nodes <= 5000
- • -5000 <= Node.val <= 5000
Hints & approach
Hint 1
As you walk the list, point each node back at the one before it.
Hint 2
You need three references: previous, current, and the next node you are about to lose.
Approachtry the hints first
Walk the list with prev = null and curr = head. At each step save next = curr.next, set curr.next = prev, then advance prev = curr and curr = next. When curr becomes null, prev is the new head. The recursive version reverses the rest of the list first, then sets head.next.next = head and head.next = null, at the cost of O(n) stack.
Time O(n) · Space O(1)