Leetcode: Remove nth node from end of list
Given the head
of a linked list, remove the nth
element from the end of the list and return the head of the list. As a follow-up, this should be done with one iteration.
The most obvious solution is to count the number of elements in the list in one iteration. This is necessary, because we don’t know initially how long the list is. Then iterate over the list again and once the index is reached, set pointer = pointer.next
. This way the nth
element is skipped.
However, there is a more elegant way to achieve this.
We can set up two pointers, both at the head
of the list. We move the first pointer and increment a counter. When the counter reaches n
, we start moving the second pointer as well. Once the first pointer reaches the end of the list we simply set the second pointer to the next position and we’re done.
There is one special case: When the element that should be removed is the first element. Because we have a pointer to head
and return head
in the end, this would be discarded. A quick solution is to create a temporary node and point it to the head
. Then do the operation as described above. In the end return pre_head.next
which points to the new (or old) head.
The __str__
and __repr__
methods are small helper methods that I added for easier debugging.
Runtime: 37 ms, faster than 88.56% of Python3 online submissions for Remove Nth Node From End of List. Memory Usage: 13.9 MB, less than 20.39% of Python3 online submissions for Remove Nth Node From End of List.