# Solution For Remove Nth Node From End Of List

The problem “Remove Nth Node From End Of List” on LeetCode asks us to remove the n-th node from the end of a singly linked list and return the modified list. In other words, given a linked list and an integer n, we have to remove the node from the list that is n positions away from the end of the list.

The input to the problem is a linked list represented as a chain of nodes, where each node has two fields: a value field that contains the node’s data, and a next field that contains a pointer to the next node in the list. The last node of the linked list has a next field that is NULL.

The output of the problem should be the modified linked list, where the n-th node from the end has been removed.

We can solve this problem using a two-pass algorithm, where in the first pass we count the total number of nodes in the list, and then in the second pass we remove the n-th node from the end of the list.

Here is the detailed solution using this algorithm:

1. Initialize two pointers, current and temp, to the head of the linked list.
2. Traverse the list using current pointer to count the number of nodes in the list. Let the count be N.
3. Compute the position of the node to be removed as (N – n + 1), where n is the given input.
4. If the position is 1, remove the head node and return the modified linked list.
5. If the position is greater than 1, set the temp pointer to the node at position (position – 1).
6. Set the next field of the node pointed to by temp to the node pointed to by the next field of temp.
7. Return the modified linked list.

Here is the implementation of the above algorithm in Python:

“`
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
# Step 1: Initialize pointers current and temp to the head of the linked list
# Step 2: Traverse the list to count the number of nodes in the list
count = 0
while current:
count += 1
current = current.next
# Step 3: Compute the position of the node to be removed
position = count – n + 1
# Step 4: If the position is 1, remove the head node and return the modified linked list
if position == 1:
# Step 5: If the position is greater than 1, set the temp pointer to the node at position (position – 1)
for i in range(position – 2):
temp = temp.next
# Step 6: Set the next field of the node pointed to by temp to the node pointed to by the next field of temp
temp.next = temp.next.next
# Step 7: Return the modified linked list
“`

The time complexity of this solution is O(n), where n is the number of nodes in the linked list, since we do a two-pass traversal of the list. The space complexity is O(1), since we use a constant amount of extra memory.

## Step by Step Implementation For Remove Nth Node From End Of List

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//edge case
}

//create two pointers, slow and fast
//advance fast pointer n+1 steps so that when it reaches the end, slow pointer will be pointing to the node we want to delete
for(int i=0; i

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0)
#initialize two pointers fast and slow
fast = slow = dummy
#move the fast pointer n+1 steps ahead of the slow pointer
for i in range(n+1):
fast = fast.next
#move both pointers together until the fast pointer reaches the end of the list
while fast:
fast = fast.next
slow = slow.next
#remove the node at the slow.next position
slow.next = slow.next.next
return dummy.next//Given a linked list, remove the n-th node from the end of list and return its head.

/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
let prev = null;

while(n > 0){
fast = fast.next;
n--;
}

while(fast !== null){
prev = slow;
slow = slow.next;
fast = fast.next;
}

if(prev === null){
return slow.next;
}

prev.next = slow.next;

};/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// Base case
return NULL;
}

// Two pass algorithm
// 1. Calculate the length of the list
int length = 0;
while (curr != NULL) {
length++;
curr = curr->next;
}

// 2. Remove the nth node from the end
int count = 0;
ListNode* prev = NULL;
while (count < length - n) {
prev = curr;
curr = curr->next;
count++;
}

// Remove the node
if (prev == NULL) {
// This is the case where we need to remove the head node
} else {
prev->next = curr->next;
}

delete curr;

}
};/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode RemoveNthFromEnd(ListNode head, int n) {
//Create a dummy node to avoid null exception when head needs to be removed
ListNode dummy = new ListNode(0);

//Create two pointers - slow and fast
ListNode slow = dummy;
ListNode fast = dummy;

//Move the fast pointer n+1 steps ahead of the slow pointer
for(int i = 0; i <= n; i++)
{
fast = fast.next;
}

//Move both pointers together until fast pointer reaches the end
while(fast != null)
{
slow = slow.next;
fast = fast.next;
}

//Remove the node next to the slow pointer
slow.next = slow.next.next;

return dummy.next;
}
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]