Given the head of a singly linked list, reverse the list and return the new head. Try to do it by changing the next pointers in place, without creating new nodes.
Example 1
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2
Input: head = [1,2]
Output: [2,1]
Example 3
Input: head = []
Output: []
Constraints
- The list has 0 to 5000 nodes
- -5000 <= Node.val <= 5000
Hints
Frequently asked at: Amazon, Microsoft, Apple, Adobe, TCS, Infosys
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The simple way stores all values in an array, then writes them back in reverse, which is O(n) extra space. To reverse in place, flip each arrow as you pass it. The only danger is losing the rest of the list once curr.next is overwritten, so we save it first. Three pointers (prev, curr, next) are enough, giving O(n) time and O(1) space. When curr becomes null, prev is the new head.
Algorithm
- Set
prev = nullandcurr = head. - While
curris not null: savenxt = curr.next. - Point
curr.next = prev(flip the arrow). - Move forward:
prev = curr,curr = nxt. - Return
prev.
Time:
O(n)Space: O(1)Interview tip: Interviewers almost always ask for the recursive version next: reverse the rest, then set
head.next.next = head and head.next = null. Mention that recursion uses O(n) stack space, which can overflow for very long lists.class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: prev, curr = None, head while curr: nxt = curr.next # save the rest of the list curr.next = prev # flip the arrow prev = curr curr = nxt return prev # new headCtrl + Enter runs the examples