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

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.

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

// Input
const head = new Node(42); // ... then add more nodes
// 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

Breakdown

Loading...

Table of Contents

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.

Loading...

Table of Contents

Test Results

Run your code and see results here...

const mirrorDelete = (head, k) => {
  // Your solution here
};
// Upgrade for full course access
// Upgrade for full course access

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.

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

// Input
const head = new Node(42); // ... then add more nodes
// 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
const mirrorDelete = (head, k) => {
  // Your solution here
};
// Upgrade for full course access
// Upgrade for full course access