Remove Kth Node From End

tags:Linked List Medium

Problem

Write a function that takes in the head of a Singly Linked List and an integer k and removes the kth node from the end of the list.
The removal should be done in place, meaning that the original data structure should be mutated (no new structure should be created).
Furthermore, the input head of the linked list should remain the head of the linked list after the removal is done, even if the head is the node that's supposed to be removed. In other words, if the head is the node that's supposed to be removed, your function should simply mutate its value and next pointer.
Note that your function doesn't need to return anything.
You can assume that the input Linked List will always have at least two nodes and, more specifically, at least k nodes.
Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None / null if it's the tail of the list.

Sample Input

head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 // the head node with value 0
k = 4

Sample Output

// No output required.
// The 4th node from the end of the list (the node with value 6) is removed.
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9

---

Solutions

Official

// O(n) time | O(1) space
function removeKthNodeFromEnd(head, k) {
  let counter = 1;
  let first = head;
  let second = head;
  while (counter <= k) {
    second = second.next;
    counter++;
  }
  if (second === null) {
    head.value = head.next.value;
    head.next = head.next.next;
    return;
  }
  while (second.next !== null) {
    second = second.next;
    first = first.next;
  }
  first.next = first.next.next;
}

---

Everyone's

月

/* Time: O(n)
   Space: O(1)
   n is the number of nodes. 
*/
function removeKthNodeFromEnd(head, k) {
  let fast = head, slow = head;
  while(k > 0){
    fast = fast.next;
    k--;
  };
  if(!fast){ // Edge Case: Is target is 1st.
    head.value = head.next.value;
    head.next = head.next.next;
    return head
  }
  while(fast.next){  // cant use !fast. For subsequent judgment
    fast = fast.next;
    slow = slow.next;
  }
  if(!slow.next.next){ // Edge Case: Is target is last.
    slow.next = null;
  }else{
    slow = slow.next;
    slow.value = slow.next.value;
    slow.next = slow.next.next;
  }
  return head
}

Two Loops

Hao

/**
 * Time complexity: O(n) where n stands for linkedList.length
 * Space complexity: O(1)
 */

// This is an input class. Do not edit.
class LinkedList {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function removeKthNodeFromEnd(head, k) {
  const dummy = new LinkedList(0);
  dummy.next = head;

  let length = 0;
  let runningNode = dummy;

  while (runningNode) {
    length += 1;
    runningNode = runningNode.next;
  }

  const removeIdx = length - k;
  let nextIdx = 0;
  runningNode = dummy;

  while (runningNode) {
    nextIdx += 1;
    if (nextIdx === removeIdx) runningNode.next = runningNode.next.next;

    runningNode = runningNode.next;
  }

  return dummy.next;
}

東

// O(n) Time | O(1) space - n is the number of nodes of linkedList
function removeKthNodeFromEnd(head, k) {
  const nodePositionFromBegin = getTotalNodeCount(head) - k + 1;
  if (nodePositionFromBegin === 1) {
    head.value = head.next.value;
    head.next = head.next.next;
    return;
  }
  let prevNode = head;
  let currNode = head.next;
  let currPosition = 2;
  while(currPosition !== nodePositionFromBegin) {
    currPosition++;
    prevNode = prevNode.next;
    currNode = currNode.next;
  }
  prevNode.next = currNode.next;
}

function getTotalNodeCount(head) {
  let count = 0;
  let currNode = head;
  while(currNode){
    count++;
    currNode = currNode.next;
  }
  return count;
}

YC

/* 
  time: O(n) - where n is the number of the nodes in the linked list
  space: O(1);
*/
// This is an input class. Do not edit.
function removeKthNodeFromEnd(head, k) {
  let node = head;
  let length = 1;
  
  //get length
  while(node.next){
    length++;
    node = node.next;
  }

  //remove
  node = head;
  // 1. the head is the node that supposed to be removed
  if(length - k === 0){
    node.value = node.next.value;
    node.next = node.next.next;
    return;
  }

  // 2. the node except for the head supposed to be removed
  let count = 1;
  while(count < length - k){
    count++;
    node = node.next;
  }
  node.next = node.next.next;;
}

---

Supplement / Discussion