Remove Kth Node From End

Category: Linked Lists

```

Problem Statement

Remove Kth Node From End 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. 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. You can assume that the input Linked List will always have at least k nodes. Sample Input head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 // the head node with value 0 k = 4 Sample Output -> 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9 Hints Hint 1 Since you are given a Singly Linked List, you do not have access to any of the list's nodes' previous nodes. Thus, traversing the entire list and then counting k nodes back isn't an option. Is there a way for you to traverse the entire list and to know which node is the kth node from the end by the time you reach the nal node in the list? Hint 2 Can you accomplish the task mentioned in Hint #1 by traversing the list all the while keeping track of two nodes at a time. How could this work? Hint 3 Initialize two variables pointing to the rst node in the list. Traverse k nodes in the list, updating the second variable at every node (that is, take k steps with the second variable). Then, traverse the remainder of the list, this time updating both the second and the rst variables (that is take as many steps with the rst variable as the number of steps between the kth node from the start and the end of the list). Once you reach the end of the list, the rst variable should point to the kth node from the end. Optimal Space & Time Complexity O(n) time | O(1) space - where n is the number of nodes in the Linked List

```

Approach & Solution

Solution 1

```java class Program { // O(n) time | O(1) space public static void removeKthNodeFromEnd(LinkedList head, int k) { int counter = 1; LinkedList first = head; LinkedList 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; } static class LinkedList { int value; LinkedList next = null; public LinkedList(int value) { this.value = value; } } }

```

Test Cases

``` Test Case 1 { "linkedList": { "head": "0", "nodes": [ {"id": "0", "next": "1", "value": 0}, {"id": "1", "next": "2", "value": 1}, {"id": "2", "next": "3", "value": 2}, {"id": "3", "next": "4", "value": 3}, {"id": "4", "next": "5", "value": 4}, {"id": "5", "next": "6", "value": 5}, {"id": "6", "next": "7", "value": 6}, {"id": "7", "next": "8", "value": 7}, {"id": "8", "next": "9", "value": 8}, {"id": "9", "next": null, "value": 9} ] }, "k": 4 } Test Case 2 { "linkedList": { "head": "0", "nodes": [ {"id": "0", "next": "1", "value": 0}, {"id": "1", "next": "2", "value": 1}, {"id": "2", "next": "3", "value": 2}, {"id": "3", "next": "4", "value": 3}, {"id": "4", "next": "5", "value": 4}, {"id": "5", "next": "6", "value": 5}, {"id": "6", "next": "7", "value": 6}, {"id": "7", "next": "8", "value": 7}, {"id": "8", "next": "9", "value": 8}, {"id": "9", "next": null, "value": 9} ] }, "k": 1 } Test Case 3 { "linkedList": { "head": "0", "nodes": [ {"id": "0", "next": "1", "value": 0}, {"id": "1", "next": "2", "value": 1}, {"id": "2", "next": "3", "value": 2}, {"id": "3", "next": "4", "value": 3}, {"id": "4", "next": "5", "value": 4}, {"id": "5", "next": "6", "value": 5}, {"id": "6", "next": "7", "value": 6}, {"id": "7", "next": "8", "value": 7}, {"id": "8", "next": "9", "value": 8}, {"id": "9", "next": null, "value": 9} ] }, "k": 2 } Test Case 4 { "linkedList": { "head": "0", "nodes": [ {"id": "0", "next": "1", "value": 0}, {"id": "1", "next": "2", "value": 1}, {"id": "2", "next": "3", "value": 2}, {"id": "3", "next": "4", "value": 3}, {"id": "4", "next": "5", "value": 4}, {"id": "5", "next": "6", "value": 5}, {"id": "6", "next": "7", "value": 6}, {"id": "7", "next": "8", "value": 7}, {"id": "8", "next": "9", "value": 8}, {"id": "9", "next": null, "value": 9} ] }, "k": 3 } Test Case 5 { "linkedList": { "head": "0", "nodes": [ {"id": "0", "next": "1", "value": 0}, {"id": "1", "next": "2", "value": 1}, {"id": "2", "next": "3", "value": 2}, {"id": "3", "next": "4", "value": 3}, {"id": "4", "next": "5", "value": 4}, {"id": "5", "next": "6", "value": 5}, {"id": "6", "next": "7", "value": 6}, {"id": "7", "next": "8", "value": 7}, {"id": "8", "next": "9", "value": 8}, {"id": "9", "next": null, "value": 9} ] }, "k": 5 } Test Case 6 { "linkedList": { "head": "0", "nodes": [ {"id": "0", "next": "1", "value": 0}, {"id": "1", "next": "2", "value": 1}, {"id": "2", "next": "3", "value": 2}, {"id": "3", "next": "4", "value": 3}, {"id": "4", "next": "5", "value": 4}, {"id": "5", "next": "6", "value": 5}, {"id": "6", "next": "7", "value": 6}, {"id": "7", "next": "8", "value": 7}, {"id": "8", "next": "9", "value": 8}, {"id": "9", "next": null, "value": 9} ] }, "k": 6 } Test Case 7 { "linkedList": { "head": "0", "nodes": [ {"id": "0", "next": "1", "value": 0}, {"id": "1", "next": "2", "value": 1}, {"id": "2", "next": "3", "value": 2}, {"id": "3", "next": "4", "value": 3}, {"id": "4", "next": "5", "value": 4}, {"id": "5", "next": "6", "value": 5}, {"id": "6", "next": "7", "value": 6}, {"id": "7", "next": "8", "value": 7}, {"id": "8", "next": "9", "value": 8}, {"id": "9", "next": null, "value": 9} ] }, "k": 7 } Test Case 8 { "linkedList": { "head": "0", "nodes": [ {"id": "0", "next": "1", "value": 0}, {"id": "1", "next": "2", "value": 1}, {"id": "2", "next": "3", "value": 2}, {"id": "3", "next": "4", "value": 3}, {"id": "4", "next": "5", "value": 4}, {"id": "5", "next": "6", "value": 5}, {"id": "6", "next": "7", "value": 6}, {"id": "7", "next": "8", "value": 7}, {"id": "8", "next": "9", "value": 8}, {"id": "9", "next": null, "value": 9} ] }, "k": 8 } Test Case 9 { "linkedList": { "head": "0", "nodes": [ {"id": "0", "next": "1", "value": 0}, {"id": "1", "next": "2", "value": 1}, {"id": "2", "next": "3", "value": 2}, {"id": "3", "next": "4", "value": 3}, {"id": "4", "next": "5", "value": 4}, {"id": "5", "next": "6", "value": 5}, {"id": "6", "next": "7", "value": 6}, {"id": "7", "next": "8", "value": 7}, {"id": "8", "next": "9", "value": 8}, {"id": "9", "next": null, "value": 9} ] }, "k": 9 } Test Case 10 { "linkedList": { "head": "0", "nodes": [ {"id": "0", "next": "1", "value": 0}, {"id": "1", "next": "2", "value": 1}, {"id": "2", "next": "3", "value": 2}, {"id": "3", "next": "4", "value": 3}, {"id": "4", "next": "5", "value": 4}, {"id": "5", "next": "6", "value": 5}, {"id": "6", "next": "7", "value": 6}, {"id": "7", "next": "8", "value": 7}, {"id": "8", "next": "9", "value": 8}, {"id": "9", "next": null, "value": 9} ] }, "k": 10 }