LeetCode #19 - Remove Nth Node From End Of List
Hello LeetCode enthusiasts ! Its time to look the nineteenth problem from LeetCode.
- Remove Nth Node From End Of List
Problem Statement
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Follow up: Could you do this in one pass?
Constraints:
The number of nodes in the list is sz.
- 1 sz 30
- 0 Node.val 100
- 1 n sz
Examples
Example 1:
Example 2:
Example 3:
Analysis
We are given a linked list and a number n, and we are required to remove the nth from the end of the list. Since we are removing the nth node, we need to link next pointer of [n - 1]th node to the [n + 1]th node.
Once we remove the node, we need to return the head of the modified list.
Approach
The intuitive approach can be like that move to the end of the list and then count n nodes backwards. This works but since the given linked list is a singly linked list [where previous pointer is not present], therefore, we need to maintain the previous pointer in every step.
Also, this approach requires two traversals of the linked list, which is an overkill.
So, do we have another way to solve this? Of course, we have using Two Pointer Technique.
Two Pointer Technique
This technique is used to solve multiple linked list problems. In this, we use two pointers, slow and fast. The fast pointer sometimes
- Move faster than the slow pointer [two steps at a time, for example]
- Move ahead of the slow pointer with same speed [n steps ahead, for example]
This problem also requires usage of two pointer technique where both pointers move with same speed but fast pointer is n steps ahead of slow pointer.
Imagine there are two bikers both riding Lightning LS-218 at top speed [which is 351 km/h ] but from different points A and B 100 km apart [B = 100 + A]. Assuming they are riding with same speed then when the biker who started from A travelled 200 km, the biker would also have travelled 200 km but would be at 300 km mark [100 + 200].
We can assume biker at A as slow pointer and biker at B as fast pointer [not that As speed is slow but it is behind 100 km].
Applying the same logic here, we can follow below steps
- Initialize two pointers slow and fast, pointing to the head of the linked list.
- Move fast pointer n steps ahead.
- Now, move both slow and fast one step at a time unless fast reaches to the end. The fast pointer will definitely reach to the end before slow because it is ahead.
- When we fast pointer reaches to the end, the slow pointer will be n steps behind it i.e., n steps behind the end of the list.
- At that point, we will remove the node and link it to the next of current node.
Thus, we only have to traverse the list only once which is more efficient.
Time Complexity
We are traversing the list only once, hence the time complexity is O[n], where n is the number of nodes in the list.
Space Complexity
We are not using any data structure for intermediate calculation, hence the space complexity will be O[1].