Back to course home
0% completed
Vote For New Content
Solution: Remove Nth Node From End of List
Problem Statement
Given a linked list, remove the last nth
node from the end of the list and return the head of the modified list.
Example 1:
- Input: list = 1 -> 2 -> 3 -> 4 -> 5, n = 2
- Expected Output: 1 -> 2 -> 3 -> 5
- Justification: The 2nd node from the end is "4", so after removing it, the list becomes [1,2,3,5].
Example 2:
- Input: list = 10 -> 20 -> 30 -> 40, n = 4
- Expected Output: 20 -> 30 -> 40
- Justification: The 4th node from the end is "10", so after removing it, the list becomes [20,30,40].
Example 3:
- Input: list = 7 -> 14 -> 21 -> 28 -> 35, n = 3
- Expected Output: 7 -> 14 -> 28 -> 35
- Justification: The 3rd node from the end is "21", so after removing it, the list becomes [7,14,28,35].
Constraints:
- The number of nodes in the list is
sz
. 1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
Solution
-
Two-Pass Approach:
- Begin by calculating the length of the linked list. This can be done by traversing the list from the head to the end.
- Once the length is determined, calculate which node to remove by subtracting
n
from the length. - Traverse the list again and remove the node at the calculated position.
-
One-Pass Approach using Two Pointers:
- Use two pointers,
first
andsecond
, and place them at the start of the list. - Move the
first
pointern
nodes ahead in the list. - Now, move both
first
andsecond
pointers one step at a time until thefirst
pointer reaches the end of the list. Thesecond
pointer will now ben
nodes from the end. - Remove the node next to the
second
pointer.
- Use two pointers,
-
Advantage of One-Pass Approach:
- The one-pass approach is more efficient as it traverses the list only once, whereas the two-pass approach requires two traversals.
-
Edge Cases:
- If
n
is equal to the length of the list, remove the head of the list.
- If
Algorithm Walkthrough
Using the input list = [1,2,3,4,5], n = 2:
- Initialize two pointers,
first
andsecond
, at the head of the list. - Move the
first
pointer 2 nodes ahead. Now,first
points to "3" andsecond
points to "1". - Move both
first
andsecond
pointers one step at a time. Whenfirst
reaches "5",second
will be at "3". - The next node to
second
is "4", which is the node to be removed. - Remove "4" by updating the next pointer of "3" to point to "5".
- The modified list is [1,2,3,5].
Code
Python3
Python3
. . . .
Complexity Analysis
- Time Complexity: O(L) - We traverse the list with two pointers. Here, L is the number of nodes in the list.
- Space Complexity: O(1) - We only used constant extra space.
.....
.....
.....
Like the course? Get enrolled and start learning!
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible