0
$\begingroup$

Question: 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.

The Solution:

class LinkedList {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function removeKthNodeFromEnd(head, k) {
  let first = head;
    let second = head;
    let i = 1;
    while(i <= k){
        second = second.next;
        i++
    }
    if(second == null){
        head.value = head.next.value; // Why can't I do: head = head.next
        head.next = head.next.next;
        return
    }
    
    while(second.next !==null){
        second = second.next;
        first = first.next;
    }
    first.next = first.next.next;
    
}

I have understood the above algorithm for the most part. Except why I need to have:

        head.value = head.next.value; 
        head.next = head.next.next;

Why can't I just replace the above lines with a single:

head = head.next
$\endgroup$
1
$\begingroup$
head = head.next

would accomplish nothing. It would only change the local variable head.

Read the question again:

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.

Since you cannot change what node is the head, you change the contents of that node.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.