Remove the Kth Node from the End of a Linked List | Skilled.dev
Interview Question

Mirror Delete

Course launching August 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

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 node and an integer k, write a function mirrorDelete that removes the kth element back from the tail node in one pass.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// Input
const head = new Node(42);
// k = 5     4     3    2    1    0
       42 -> 52 -> 4 -> 6 -> 1 -> 9000


// Output: mirroDelete(head, 2)
// Remove k = 2 which is the 6
42 -> 52 -> 4 -> 1 -> 9000

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.