Interview Question
Share Lesson

# Mirror Delete

You are given the head `Node` 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:

1. Iterate through the linked list in one pass.
2. You don't know the size of the linked list.
3. `k >= 0`
4. The tail node is considered the `k = 0` element.
5. 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

Share:

### Validate My Answer

1. 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.

2. 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.

3. 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.

4. Make sure you account for any `k >= 0`. Test where `k` is 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.

Share:

Test Results

Run your code and see results here...

### Mirror Delete

You are given the head `Node` 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:

1. Iterate through the linked list in one pass.
2. You don't know the size of the linked list.
3. `k >= 0`
4. The tail node is considered the `k = 0` element.
5. 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.

`` ``