Given the head of a singly linked list and an integer n, remove the nth node from the back of the linked list and return the updated head.
The value of n stays between 1 and the length of the linked list. The deletion can affect the first node, a middle node, or the last node.
Example 1
Input: head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Explanation: The second node from the back has value 4, so deletion produces [1, 2, 3, 5].
Example 2
Input: head = [1], n = 1
Output: []
Explanation: The only node is removed, so the updated linked list becomes empty.
Approach 1
First, we count the total number of nodes in the linked list. Using the length, we determine the position of the node just before the one to be deleted. A dummy node is used to simplify cases where the head node needs to be removed.
Algorithm
Traverse the linked list once to count the total number of nodes, as the position of the node from the end can be determined using the list length.
Create a dummy node and connect it to
head, as this also handles the case where the target node is the original head.Compute
steps = length - n, since this gives the number of positions needed to reach the node immediately before thenth node from the end.Move a pointer from the dummy node by
stepspositions, so it reaches the node whosenextpointer refers to the target node.Update this pointer's
nexttocurrent->next->next, which bypasses the target node while keeping the remaining list connected.Return
dummy->nextas the updated head, since the dummy node allows the head to change safely when the first node is removed.
Dry Run
remove nth node
Solution
#include <bits/stdc++.h>using namespace std;struct ListNode { int data; ListNode* next; ListNode(int value) { data = value; next = nullptr; }};class Solution {public: // Function to remove nth node from back using length counting. ListNode* removeNthFromEnd(ListNode* head, int n) { int length = 0; ListNode* current = head; // Count total nodes. while (current != nullptr) { length++; current = current->next; } ListNode dummy(0); dummy.next = head; ListNode* previous = &dummy; int steps = length - n; // Move to node before deletion target. for (int index = 0; index < steps; index++) { previous = previous->next; } // Bypass deletion target. previous->next = previous->next->next; return dummy.next; }};// Function to create linked list from array.ListNode* createList(vector<int>& arr) { ListNode dummy(0); ListNode* tail = &dummy; for (int value : arr) { tail->next = new ListNode(value); tail = tail->next; } return dummy.next;}// Function to print linked list values.void printList(ListNode* head) { ListNode* current = head; while (current != nullptr) { cout << current->data; if (current->next != nullptr) cout << " "; current = current->next; }}// Driver code.int main() { vector<int> arr = {1, 2, 3, 4, 5}; int n = 2; ListNode* head = createList(arr); Solution sol; head = sol.removeNthFromEnd(head, n); printList(head); return 0;}Complexity Analysis
Time Complexity: O(N), every node is visited during counting and at most once more during positioning.
Space Complexity: O(1), only a few pointers and counters are used.
Approach 2
This approach maintains a gap of n nodes between two pointers. After advancing the fast pointer by n nodes, both fast and slow move together until fast reaches the last node. At this point, slow is positioned just before the node that needs to be removed. A dummy node simplifies deletion when the head node is the target.
Algorithm
Create a dummy node and connect it to
head, as this provides a node before the first element and makes removing the head follow the same logic as removing any other node.Initialize both
fastandslowat the dummy node, since maintaining a gap ofnnodes between them will allowslowto reach the node just before the target.Move the
fastpointernnodes ahead, creating the required distance between the two pointers.Move both pointers one step at a time until
fast->nextbecomesNULL, as this placesslowimmediately before thenth node from the end.Update
slow->nexttoslow->next->next, which bypasses the target node while keeping the remaining nodes connected.Return
dummy->nextas the updated head, since the dummy node also handles the case where the original head is the node being removed.
Dry Run
remove nth node
Solution
#include <bits/stdc++.h>using namespace std;struct ListNode { int data; ListNode* next; ListNode(int value) { data = value; next = nullptr; }};class Solution {public: // Function to remove nth node from back using two pointers. ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); dummy.next = head; ListNode* fast = &dummy; ListNode* slow = &dummy; // Create n-node gap between fast and slow. for (int count = 0; count < n; count++) { fast = fast->next; } // Move until fast reaches last node. while (fast->next != nullptr) { fast = fast->next; slow = slow->next; } // Bypass deletion target. slow->next = slow->next->next; return dummy.next; }};// Function to create linked list from array.ListNode* createList(vector<int>& arr) { ListNode dummy(0); ListNode* tail = &dummy; for (int value : arr) { tail->next = new ListNode(value); tail = tail->next; } return dummy.next;}// Function to print linked list values.void printList(ListNode* head) { ListNode* current = head; while (current != nullptr) { cout << current->data; if (current->next != nullptr) cout << " "; current = current->next; }}// Driver code.int main() { vector<int> arr = {1, 2, 3, 4, 5}; int n = 2; ListNode* head = createList(arr); Solution sol; head = sol.removeNthFromEnd(head, n); printList(head); return 0;}Complexity Analysis
Time Complexity: O(N), the fast pointer traverses the list once while the slow pointer follows behind.
Space Complexity: O(1), only constant extra pointers are used.
Interview follow-up Questions
Yes. A dummy node before the head allows first-node deletion without special handling.
Be the first to add a comment.