Remove Nth Node From End of List
MediumThe problem
Given the head of a linked list and a number n, remove the n-th node counting from the END of the list (n = 1 is the last node), and return the head of the list.
- Example 1Input: head = [1, 2, 3, 4, 5], n = 2Output: [1, 2, 3, 5]
The 2nd node from the end is 4, so it is removed.
- Example 2Input: head = [1], n = 1Output: []
Removing the only node leaves an empty list.
- Example 3Input: head = [1, 2], n = 1Output: [1]
The last node (2) is removed.
Limits
- 1 ≤ number of nodes ≤ 30,000
- 1 ≤ n ≤ number of nodes
- 0 ≤ node value ≤ 100
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
Can two markers that are n nodes apart find the position in one pass?
The idea
Dummy head; move fast n steps ahead, then move both until fast reaches the end; slow.next is the node to remove.
Target: O(n) time, O(1) space
Go function shape
func removeNthFromEnd(head *ListNode, n int) *ListNodeReference solution
Tested with go test. Try it yourself first, then compare.
// RemoveNthFromEnd: remove the nth node from the end in one pass.
// fast gets an n-step head start, so when fast reaches the end, slow is just before the target.
func RemoveNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{Next: head} // lets us delete the real head without a special case
fast, slow := dummy, dummy
for i := 0; i < n && fast != nil; i++ {
fast = fast.Next
}
if fast == nil { // n is larger than the list: nothing to remove
return head
}
for fast.Next != nil {
fast, slow = fast.Next, slow.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}