Table of Contents
Problem Statement
The Remove Nth Node From End of List Leetcode Solution – states that you are given the head of a linked list and you need to remove the nth node from the end of this list.
After deleting this node, return the head of the modified list.
Example:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation:
- We have to remove the second node from the end of the list, the node with value 4.
- After deleting this node, we have the modified list containing all the elements as [1,2,3,5].
Input: head = [1], n = 1
Output: []
Explanation:
- We need to remove the end node of the list.
- After removing the node, we have an empty list.
Approach
Idea:
- The main idea to solve this problem is to use three variables that store the node’s addresses.
- curr = It will store the current node’s address used to iterate in the linked list.
- start = It will store the node’s address that will be deleted (nth node from the end of the list).
- prev = It will store the previous node’s address of the node’s start.
- Note that, the distance between the deleting node and head of the linked list is m-n and the distance between deleting node and end of the linked list is n, where m = length of linked list.
- The above observation suggests that start the curr variable from the head of the linked list and decrement n each time as we move forward in the linked list. As soon as we have n as a non-positive value, initialize the start variable with the address of the head of the linked list and increment the start variable as well as the prev variable each time when n is non-positive.
- Step 3 works efficiently since whatever the distance curr variable covers after n becomes non-positive, will be equal to the distance covered by the start variable from the head of the linked list which is m-n. Hence, we’ll end up with the nth node from the end’s address stored in the start variable.
- Delete the node contained in the start variable, by assigning prev next node address as the start next address.
- Check code for better understanding.
Code
Remove Nth Node From End of List Leetcode C++ Solution:
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *prev = nullptr,*curr = head,*start = nullptr;
while(curr!=nullptr){
n--;
curr = curr->next;
if(n<=0){
if(start==nullptr){
start = head;
}
else{
prev = start;
start = start->next;
}
}
}
if(prev==nullptr){
return start->next;
}
prev->next = start->next;
return head;
}
};Remove Nth Node From End of List Leetcode Java Solution:
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode curr = head;
ListNode prev = null;
ListNode start = null;
while(curr!=null){
n = n - 1;
curr = curr.next;
if(n<=0){
if(start==null){
start = head;
}
else{
prev = start;
start = start.next;
}
}
}
if(prev==null){
return start.next;
}
prev.next = start.next;
return head;
}
}Complexity Analysis for Remove Nth Node From End of List Leetcode Solution
Time Complexity
The time complexity of the above code is O(N), where N = length of the linked list since we’re iterating for the entire linked list one time.
Space Complexity
The space complexity of the above code O(1) since we’re using constant extra space.