Question
Given theÂ
head of a linked list, remove theÂnth node from the end of the list and return its head.
This is alinked_list question.
Idea
- Count the number of nodes in the linked list using a dummy pointer
- Find the number of nodes from the head to remove by taking the difference between the number of nodes in the list and the number of nodes from the end of the list
- Consider the edge cases
- If there is only one node in the list, return None
- If we want to remove the head, return head.next
- Iterate until the node we want to remove
- If there is a node after the node we want to remove, set dummy.next = dummy.next.next
- Otherwise, set dummy.next = None
- Return head
Optimized Solution
- Establish a dummy, left, and right pointer as a node pointing to the head
- Increment right n+1 times (+1 since right points to the head and is not the head)
- While right is not None, increment both left and right pointers and when right is None, left will be the node before the node to remove
- Skip the node to remove (left.next = left.next.next)
- Return dummy.next