A linked list operates as a chain of connected elements, with each element aware of the next one in line. In this article, we will explore different approaches to remove the nth node from the end of a linked list with implementation in C++, Java, and Python.
Removing the nth Node from the End of the List
When we discuss removing the nth element from the end of the linked list, we’re essentially targeting the element positioned at the nth spot when counting backward from the end of the list. In simpler terms, it’s like removing the element that holds the nth position from the list’s tail.
In this problem, we are given a linked list and a value of n and we have to remove a node that holds the nth position from the list’s tail.
Let us understand it better with an example:
List nodes = [1,2,3,4,5,6]
n = 2
Output = [1,2,3,4,6]
The second node from the end has a value of 5, we will remove that node. So our output list becomes [1,2,3,4,6].
Brute Force Approach
In the brute force approach to solve this problem, we have to first count the length of the linked list for this we have to traverse a linked list once to count the length and traverse again to delete the nth node, nth node from the last is the length – nth node from starting.
Steps to solve this problem:
- In the first step, we will initialize a variable length to 0 and use a while loop to traverse the linked list and count the number of nodes. After this loop, the length will contain the total number of nodes in the linked list.
- In the second step, we will create a dummy node with a value of 0 and set its next pointer to the head of the original linked list. This dummy node is used to simplify handling edge cases where the head of the list needs to be removed.
- In this step, we will use a loop to move the current pointer to the node just before the one to be removed. The loop runs for length – n iterations.
- Finally, we will adjust the next pointer of the current node to skip over the nth node, effectively removing it from the linked list.
The time complexity of the brute force approach is O(n), where n is the number of nodes in the linked list. The space complexity is O(1) as we haven’t used any additional space.
Two Pointer Approach
We can avoid the hassle of counting the length of the list by using the two-pointers. Two-Pointers are a good approach to removing the nth node from the end of a linked list. Let’s see the steps of how we can solve this problem:
- We will create a new ListNode named ‘dummy’ with an empty value. Set the next ‘dummy’ to the head of the linked list.
- Now we will create two pointers, ‘fast’ and ‘slow’, both initially pointing to ‘dummy’.
- Now we will Move the ‘fast’ pointer n steps ahead in the linked list.
- Now we will Move both ‘slow’ and ‘fast’ pointers until the fast’s next is not NULL
- Now we will Remove the nth node from the end by adjusting pointers.
C++ Code
Below is the C++ program to remove the nth node from end of a list:
#include <iostream>
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* removeNthFromEnd(ListNode* head, int n) {
// Step 1: Create a new ListNode named 'start' with an empty value.
ListNode* start = new ListNode(0);
// Set the next 'start' to the head of the linked list.
start->next = head;
// Step 2: Create two pointers, 'fast' and 'slow', both initially pointing to 'start'.
ListNode* fast = start;
ListNode* slow = start;
// Step 3: Move the 'fast' pointer n steps ahead in the linked list.
for (int i = 0; i < n; i++) {
fast = fast->next;
}
// Step 4: Move both 'slow' and 'fast' pointers until 'fast' reaches the end.
while (fast->next != nullptr) {
slow = slow->next;
fast = fast->next;
}
// Step 5: Remove the nth node from the end by adjusting pointers.
slow->next = slow->next->next;
// Step 6: Return the modified linked list starting from 'start->next'.
return start->next;
}
// Function to print the linked list
void printList(ListNode* head) {
while (head != nullptr) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << std::endl;
}
int main() {
// Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
head->next->next->next->next->next = new ListNode(6);
std::cout << "Original Linked List: ";
printList(head);
int n = 2; // Example: Remove the 2nd node from the end
// Remove the nth node from the end
head = removeNthFromEnd(head, n);
std::cout << "Modified Linked List: ";
printList(head);
return 0;
}Python Code
Here is the Python program for our problem:
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def removeNthFromEnd(head, n):
# Step 1: Create a new ListNode named 'start' with an empty value.
start = ListNode(0)
# Set the next of 'start' to the head of the linked list.
start.next = head
# Step 2: Create two pointers, 'fast' and 'slow', both initially pointing to 'start'.
fast = start
slow = start
# Step 3: Move the 'fast' pointer n steps ahead in the linked list.
for _ in range(n):
fast = fast.next
# Step 4: Move both 'slow' and 'fast' pointers until 'fast' reaches the end.
while fast.next is not None:
slow = slow.next
fast = fast.next
# Step 5: Remove the nth node from the end by adjusting pointers.
slow.next = slow.next.next
# Step 6: Return the modified linked list starting from 'start.next'.
return start.next
# Function to print the linked list
def printList(head):
while head is not None:
print(head.val, end=" ")
head = head.next
print()
# Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = ListNode(6)
print("Original Linked List:", end=" ")
printList(head)
n = 2 # Example: Remove the 2nd node from the end
# Remove the nth node from the end
head = removeNthFromEnd(head, n)
print("Modified Linked List:", end=" ")
printList(head)Java Code
You can implement it in Java too:
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class RemoveNthFromEnd {
public static ListNode removeNthFromEnd(ListNode head, int n) {
// Step 1: Create a new ListNode named 'start' with an empty value.
ListNode start = new ListNode(0);
// Set the next of 'start' to the head of the linked list.
start.next = head;
// Step 2: Create two pointers, 'fast' and 'slow', both initially pointing to 'start'.
ListNode fast = start;
ListNode slow = start;
// Step 3: Move the 'fast' pointer n steps ahead in the linked list.
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// Step 4: Move both 'slow' and 'fast' pointers until 'fast' reaches the end.
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// Step 5: Remove the nth node from the end by adjusting pointers.
slow.next = slow.next.next;
// Step 6: Return the modified linked list starting from 'start.next'.
return start.next;
}
// Function to print the linked list
public static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
// Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
head.next.next.next.next.next = new ListNode(6);
System.out.print("Original Linked List: ");
printList(head);
int n = 2; // Example: Remove the 2nd node from the end
// Remove the nth node from the end
head = removeNthFromEnd(head, n);
System.out.print("Modified Linked List: ");
printList(head);
}
}Output:
Original Linked List: 1 2 3 4 5 6
Modified Linked List: 1 2 3 4 6The time complexity of this approach is O(n) as the code traverses the list once using two pointers (fast and slow) until the fast reaches the end. Here n is the number of nodes in the linked list.
The space complexity is O(1) as we haven’t used any extra space.
Here is a small comparative analysis of both approaches:
| Approach | Time Complexity | Details |
| Brute Force | O(n) | First count the length of the linked list and delete the nth node from last, i.e., length – nth node from starting. |
| Two Pointes | O(n) | Create a dummy node, and use two pointers, fast and slow to traverse the list and delete the nth node from last. |
Conclusion
In conclusion, the article provides an overview of the “Remove Nth Node from End of List” leetcode problem in the context of a linked list. You can now easily implement both a naive brute-force approach and an optimized two-pointer approach.
