Reverse Linked List
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
