LeetCode Meditations: Remove Nth Node From the End of List
The description for this problem says:
Given the
headof a linked list, remove thenthnode from the end of the list and return its head.
For example:
Input: head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Input: head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
It seems like an easy question at first glance. However, the tricky thing is that the nth node is counted from the back.
Now, if we were to do it normally from the start of the list, we could just keep a count, and when the count reached the nth index, we could just unlink that node. Here is a basic example in JavaScript:
function removeNode(head, n) {
if (head === null) {
return;
}
let currentNode = head;
if (n === 0) {
head = currentNode.next;
return;
}
let count = 0;
while (currentNode !== null && count < n - 1) {
currentNode = currentNode.next;
count++;
}
if (currentNode === null || currentNode.next === null) {
return;
}
let nextNode = currentNode.next.next;
currentNode.next = nextNode;
return head;
}
function removeNode(head, n) {
if (head === null) {
return;
}
let currentNode = head;
if (n === 0) {
head = currentNode.next;
return;
}
let count = 0;
while (currentNode !== null && count < n - 1) {
currentNode = currentNode.next;
count++;
}
if (currentNode === null || currentNode.next === null) {
return;
}
let nextNode = currentNode.next.next;
currentNode.next = nextNode;
return head;
}
However, we need to do it from the back of the list. We could try traversing in reverse, but there is a solution using the fast and slow pointers technique as shown by NeetCode.
First, we'll create a dummy node with value 0, that I'm going to call result:
let result = new ListNode(0);
let result = new ListNode(0);
Then, we'll point its next pointer to head to link the original list:
result.next = head;
result.next = head;
Then, we'll initialize our fast and slow pointers:
let slow = result;
let fast = head;
let slow = result;
let fast = head;
Then, we'll bring our fast pointer to the nth node so that the number of nodes between it and the slow pointer is initially n:
while (n > 0 && fast !== null) {
fast = fast.next;
n--;
}
while (n > 0 && fast !== null) {
fast = fast.next;
n--;
}
For example, in the image given at the beginning, if n is 1, fast will be at the node with the value 2, while slow points to the dummy node with value 0. The gap between them is exactly n — that is, 1.
After that, we'll make the slow pointer catch up slowly. We'll also update fast, but the gap between them will stay as n:
while (fast !== null) {
slow = slow.next;
fast = fast.next;
}
while (fast !== null) {
slow = slow.next;
fast = fast.next;
}
At this point when fast points to null, slow will be at the previous node of the node we need to remove.
So, the only thing to do is to point its next pointer to the next of the node-to-be-removed, essentially unlinking it:
slow.next = slow.next.next;
slow.next = slow.next.next;
Eventually we can return the head which is pointed to by our dummy node's next pointer:
return result.next;
return result.next;
All in all, this is our solution in TypeScript:
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.next = (next === undefined ? null : next)
* }
* }
*/
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let result = new ListNode(0);
result.next = head;
let slow = result;
let fast = head;
while (n > 0 && fast !== null) {
fast = fast.next;
n--;
}
while (fast !== null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return result.next;
};
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.next = (next === undefined ? null : next)
* }
* }
*/
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let result = new ListNode(0);
result.next = head;
let slow = result;
let fast = head;
while (n > 0 && fast !== null) {
fast = fast.next;
n--;
}
while (fast !== null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return result.next;
};
Time and space complexity
We need to "touch" each node, so the time complexity will be linear — .
The space complexity is as we don't need extra space that grows with the input size. Note that result doesn't scale with the size of the input, it's just one node that has its next pointing to the head of the original list.
The next problem is Linked List Cycle where the fast and slow pointers technique will be useful again. Until then, happy coding.