19. Remove Nth Node From End of List
Problem Description
The problem presents us with a linked list and requires us to remove the nth node from the end of the list. A linked list is a linear collection of elements called nodes, where each node contains data and a reference (or link) to the next node in the sequence. The head
of a linked list refers to the first node in this sequence. Our goal is to remove the nth node from the last node and return the updated list's head
.
In simple terms, if we were to count nodes starting from the last node back to the first, we need to find and remove the node that sits at position 'n'. For example, if the linked list is 1->2->3->4->5
and n
is 2, the resulting linked list after the operation should be 1->2->3->5
, since the 4
is the 2nd node from the end.
The challenge with this task is that we can't navigate backwards in a singly linked list, so we need to figure out a way to reach the nth node from the end only by moving forward.
Intuition
To address the problem, we apply a two-pointer approach, which is a common technique in linked list problems. The intuition here lies in maintaining two pointers that we'll call fast
and slow
. Initially, both of these pointers will start at a dummy node that we create at the beginning of the list, which is an auxiliary node to simplify edge cases, such as when the list contains only one node, or when we need to remove the first node of the list.
The fast
pointer advances n
nodes into the list first. Then, both slow
and fast
pointers move at the same pace until fast
reaches the end of the list. At this point, slow
will be right before the node we want to remove. By updating the next
reference of the slow
pointer to skip the target node, we effectively remove the nth node from the end of the list.
The use of a dummy node is a clever trick to avoid having to separately handle the special case where the node to remove is the first node of the list. By ensuring that our slow
pointer starts before the head
of the actual list, we can use the same logic for removing the nth node, regardless of its position in the list.
After we've completed the removal, we return dummy.next
, which is the updated list's head
, after the dummy node.
Learn more about Linked List and Two Pointers patterns.
Solution Approach
The solution implements an efficient approach to solving the problem by using two pointers and a dummy node. Here's a step-by-step walkthrough of the implementation:
-
Create a Dummy Node: A dummy node is created and its
next
pointer is set to thehead
of the list. This dummy node serves as an anchor and helps to simplify the removal process, especially if thehead
needs to be removed.1dummy = ListNode(next=head)
-
Initialize Two Pointers: Two pointers
fast
andslow
are introduced and both are set to the dummy node. This allows for them to start from the very beginning of the augmented list (which includes the dummy node).1fast = slow = dummy
-
Advance Fast Pointer: The
fast
pointer advancesn
steps into the list.1for _ in range(n): 2 fast = fast.next
-
Move Both Pointers: Both pointers then move together one step at a time until the
fast
pointer reaches the end of the list. By this time,slow
is at the position right before the nth node from the end.1while fast.next: 2 slow, fast = slow.next, fast.next
-
Remove the Target Node: Once
slow
is in position, itsnext
pointer is changed to skip the target node which effectively removes it from the list.1slow.next = slow.next.next
-
Return Updated List: Finally, the next node after the dummy is returned as the new head of the updated list.
1return dummy.next
The algorithm fundamentally relies on the two-pointer technique to find the nth node from the end. The use of a dummy node facilitates the removal of nodes, including the edge case of the head
node, with a consistent method. The space complexity is O(1) since no additional space is required aside from the pointers, and the time complexity is O(L), where L is the length of the list, as we traverse the list with two pointers in a single pass.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the linked list 1->2->3->4->5
as an example to illustrate the solution approach described above, where n
is 2, meaning we want to remove the 2nd node from the end, which is the node with the value 4
. Here's how the algorithm would be applied:
-
Create a Dummy Node: We create a dummy node with
None
as its value and link it to the head of our list. Our list now looks likedummy->1->2->3->4->5
. -
Initialize Two Pointers: We set both
fast
andslow
pointers to the dummy node. They both point todummy
initially. -
Advance Fast Pointer: As
n
is 2, we advance thefast
pointern
steps into the list.fast
becomes:- After 1st step:
fast
points to1
- After 2nd step:
fast
points to2
- After 1st step:
-
Move Both Pointers: Now we move both
slow
andfast
pointers together one step at a time untilfast
reaches the last node:slow
points todummy
andfast
points to2
(Start)slow
points to1
andfast
points to3
slow
points to2
andfast
points to4
slow
points to3
andfast
points to5
(End)
At the end of this step,
slow
points to the3
andfast
points to the last node5
. -
Remove the Target Node: Now,
slow.next
is pointing to the node4
, which we want to remove. We updateslow.next
to point toslow.next.next
(which is5
), effectively removing the4
from the list. -
Return Updated List: Finally, we return the next node after the dummy, which is the
head
of our updated list (1->2->3->5
). The updated list after removal is as follows:1->2->3->5
.
The problem is solved in one pass and the node is successfully removed according to the given constraints.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, val=0, next_node=None):
4 self.val = val
5 self.next = next_node
6
7class Solution:
8 def remove_nth_from_end(self, head: ListNode, n: int) -> ListNode:
9 # Create a dummy node that points to the head of the list. This helps simplify edge cases.
10 dummy_node = ListNode(next_node=head)
11
12 # Initialize two pointers to the dummy node.
13 fast_pointer = slow_pointer = dummy_node
14
15 # Move fast pointer n steps ahead so it maintains a gap of n between slow pointer.
16 for _ in range(n):
17 fast_pointer = fast_pointer.next
18
19 # Move both pointers until fast pointer reaches the end of the list,
20 # keeping the gap of n. Thus, the slow pointer will point to the node
21 # just before the one to be removed.
22 while fast_pointer.next:
23 slow_pointer, fast_pointer = slow_pointer.next, fast_pointer.next
24
25 # Remove the nth node from the end by skipping over it with the slow pointer.
26 slow_pointer.next = slow_pointer.next.next
27
28 # Return the new head, which is the next node of dummy node.
29 return dummy_node.next
30
1// Definition for singly-linked list node.
2class ListNode {
3 int val;
4 ListNode next;
5
6 // Constructor to initialize the node without a next node
7 ListNode() {}
8
9 // Constructor to initialize the node with a value
10 ListNode(int val) { this.val = val; }
11
12 // Constructor to initialize the node with a value and a next node
13 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
14}
15
16public class Solution {
17
18 // Removes the nth node from the end of the list
19 public ListNode removeNthFromEnd(ListNode head, int n) {
20 // Create a dummy node that precedes the head of the list
21 ListNode dummyNode = new ListNode(0, head);
22
23 // Initialize two pointers, starting at the dummy node
24 ListNode fastPointer = dummyNode;
25 ListNode slowPointer = dummyNode;
26
27 // Move the fast pointer n steps ahead
28 while (n-- > 0) {
29 fastPointer = fastPointer.next;
30 }
31
32 // Move both pointers until the fast pointer reaches the end of the list
33 while (fastPointer.next != null) {
34 slowPointer = slowPointer.next;
35 fastPointer = fastPointer.next;
36 }
37
38 // Skip the node that is nth from the end
39 slowPointer.next = slowPointer.next.next;
40
41 // Return the head of the modified list, which is the next node of dummy node
42 return dummyNode.next;
43 }
44}
45
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode() : val(0), next(nullptr) {}
7 * ListNode(int x) : val(x), next(nullptr) {}
8 * ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13 // Removes the n-th node from the end of the list and returns the new head
14 ListNode* removeNthFromEnd(ListNode* head, int n) {
15 // Create a dummy node pointing to the head to handle edge cases easily
16 ListNode* dummyNode = new ListNode(0, head);
17 // These pointers will help find the node to remove
18 ListNode* fastPointer = dummyNode;
19 ListNode* slowPointer = dummyNode;
20
21 // Move fastPointer n steps ahead
22 for(int i = 0; i < n; i++) {
23 fastPointer = fastPointer->next;
24 }
25
26 // Move both pointers until fastPointer reaches the last node
27 while (fastPointer->next != nullptr) {
28 slowPointer = slowPointer->next;
29 fastPointer = fastPointer->next;
30 }
31
32 // slowPointer will be just before the node we want to remove
33 slowPointer->next = slowPointer->next->next;
34
35 // The returned head might not be the original head if the first node was removed
36 ListNode* newHead = dummyNode->next;
37 delete dummyNode; // Clean up memory used by dummyNode
38 return newHead;
39 }
40};
41
1// Type definition for a single node of a singly linked list.
2type ListNode = {
3 val: number;
4 next: ListNode | null;
5}
6
7// Function to create a new ListNode with given value and next node.
8function createListNode(val: number = 0, next: ListNode | null = null): ListNode {
9 return { val, next };
10}
11
12/**
13 * Removes the n-th node from the end of the list and returns the head of the modified list.
14 * @param {ListNode | null} head - The head of the linked list.
15 * @param {number} n - The position from the end of the list to remove the node.
16 * @returns {ListNode | null} - The head of the list after removal.
17 */
18function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
19 // Create a dummy node that will help in edge cases, like removing the first node.
20 const dummy = createListNode(0, head);
21 // Initialize two pointers, both start at the dummy node.
22 let fastPointer: ListNode | null = dummy;
23 let slowPointer: ListNode | null = dummy;
24
25 // Advance the fast pointer n steps ahead of the slow pointer.
26 for (let i = 0; i < n; ++i) {
27 fastPointer = fastPointer.next;
28 }
29
30 // Move both pointers until the fast pointer reaches the end of the list
31 while (fastPointer.next !== null) {
32 slowPointer = slowPointer.next;
33 fastPointer = fastPointer.next;
34 }
35
36 // Skip the target node by assigning its next node to the next of the slow pointer.
37 // This effectively removes the target node from the list.
38 slowPointer.next = slowPointer.next.next;
39
40 // Return the new head of the list. The dummy node's next pointer points to the list head.
41 return dummy.next;
42}
43
Time and Space Complexity
The given code is designed to remove the nth node from the end of a singly linked list. It employs the two-pointer technique with fast
and slow
pointers. Let's analyze the time and space complexity:
Time Complexity
The time complexity is determined by the number of operations required to traverse the linked list. There are two main steps in this algorithm:
- The
fast
pointer movesn
steps ahead ā this takesO(n)
time. - Both
fast
andslow
pointers move together untilfast
reaches the last node. The worst-case scenario is whenn
is 1, which would cause theslow
pointer to traverse the entire list of sizeL
(list length), takingO(L)
time.
Since the list is traversed at most once, the overall time complexity is O(L)
.
Space Complexity
The space complexity is determined by the amount of additional space used by the algorithm, which does not depend on the input size:
- The
dummy
node and the pointers (fast
andslow
) use constant extra space, regardless of the linked list's size. - Therefore, the space complexity is
O(1)
for the extra space used by the pointers and the dummy node.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we