Leetcode: Remove nth node from end of list
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.
__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.