Reverse Linked List
EasyThe problem
Given the head of a linked list, reverse the list and return the new head. (An empty list has head nil.)
- Example 1Input: head = [1, 2, 3, 4, 5]Output: [5, 4, 3, 2, 1]
The nodes now run from the old last node to the old first node.
- Example 2Input: head = [1, 2]Output: [2, 1]
- Example 3Input: head = []Output: []
An empty list stays empty.
Limits
- 0 ≤ number of nodes ≤ 5,000
- -5,000 ≤ node value ≤ 5,000
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Before you flip a node's pointer, what must you save so you do not lose the rest of the list?
The idea
Keep prev (nil) and curr; in a loop save next, point curr.next at prev, then advance both.
Target: O(n) time, O(1) space
Go function shape
func reverseList(head *ListNode) *ListNodeReference solution
Tested with go test. Try it yourself first, then compare.
// ReverseList: flip every Next pointer in place.
func ReverseList(head *ListNode) *ListNode {
var prev *ListNode
for cur := head; cur != nil; {
next := cur.Next // save it, or we lose the rest of the list
cur.Next = prev // flip the arrow
prev, cur = cur, next
}
return prev
}