Mirror Delete
You are given the head ListNode of a singly linked list and are told you need to remove an element in the list.
However, instead of being given the index relative to the head for the element you want to delete, you are told you want to remove an item k nodes back from the tail.
Constraints:
- Iterate through the linked list in one pass.
- You don't know the size of the linked list.
k >= 0- The tail node is considered the
k = 0element. - If there is no node that can be removed, return the same list.
The definition of one pass is up for debate. In this problem, we'll define it as: once your pointer reaches the tail, you can't then start another pointer at the head again.
Given a linked list head node and an integer k, write a function mirrorDelete that removes the kth element back from the tail node in one pass.
Breakdown
Approach and test strategy
Delete by a zero-based offset from the linked-list tail
Read the approach, boundary cases, and complexity
Here k equals zero for the tail, one for the preceding node, and so on. Use a leading pointer to establish the gap needed to locate the target or its predecessor in one pass. Deleting the head requires returning a different head reference. If k is at least the list length, the result remains unchanged. Trace the gap carefully rather than copying a one-based nth-from-end formula.
Cases to check
- Delete the tail with k equal to zero.
- Delete the head of a four-node list with k equal to three.
- Use k equal to the length and greater than the length; both leave the chain unchanged.
Cost model
A spaced-pointer implementation takes O(n) time and O(1) auxiliary references. The caller must receive the updated head when the original first node is removed.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
This can either be solved iteratively or recursively. The recursive solution is not more elegant and will also add O(n) space, so the best path is to tackle it iteratively.
Remember you can only use one pass on the linked list. This means as we're iterating through, we need to know exactly where our kth node is to delete it. If you introduce a second pointer with the runner technique, you could calculate that.
Remember to delete a node, you actually need to be in the spot before it on the list. Make sure your solution accounts for that.
Make sure you account for any
k >= 0. Test wherekis larger than the list, inside the list, corresponds to the head, and corresponds to the tail. There are edge cases and off-by-one issues that you need to make sure you capture.
Mirror Delete
You are given the head ListNode of a singly linked list and are told you need to remove an element in the list.
However, instead of being given the index relative to the head for the element you want to delete, you are told you want to remove an item k nodes back from the tail.
Constraints:
- Iterate through the linked list in one pass.
- You don't know the size of the linked list.
k >= 0- The tail node is considered the
k = 0element. - If there is no node that can be removed, return the same list.
The definition of one pass is up for debate. In this problem, we'll define it as: once your pointer reaches the tail, you can't then start another pointer at the head again.
Given a linked list head node and an integer k, write a function mirrorDelete that removes the kth element back from the tail node in one pass.