Data Structures
Delete Nth-to-Last Node
Given the head of a linked list head and an index i, delete the ith-to-last element, and return the new head of the linked list.
The index will always be in bounds.
To solve this problem, you have to delete the ith-to-last element:
You can solve this problem in 2 passes:
To do this, you can first find the length of the linked list n, like this:
You can then find the index of the ith-to-last element, which is n - i. To delete that element, you can use the code from the previous problem, like this:
Here's the solution, combining the above code:
Time Complexity O(n). You loop through the list twice - first to find the length, and then to delete the element. This is O(2n) = O(n).
Space Complexity O(1)
You can also solve the problem in 1 pass.
To do this, you can imagine that you're sliding a rod down the linked list, of size i+1.
When the rod hits the end of the list, then you are able to delete the ith-to-last element:
Here's the code for this:
This code works, but it breaks when you have to remove the head of the Linked List. This is because you're assuming there will always be a node L to the left of the one you want to delete, and this isn't true in that case.
To fix this, you can add a dummy node that points to the head of the Linked List. That way you'll never be asked to delete the head; there will always be the dummy node first.
Here's the code, incorporating the dummy node idea:
Here's the full code:
The dummy node idea often helps in LinkedList problems. You could have used it in the previous problem to avoid dealing with the head node deletion case too.
Time Complexity O(n). You only have 1 for-loop. You're still doing the same number of operations as before, but they happen in parallel.
Space Complexity O(1)
