# 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:

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

current = head

temp = head

# 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:

return head.next

# 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

return head

“`

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

/** * Definition for singly-linked 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 if(head == null){ return head; } //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 ListNode slow = head; ListNode fast = head; for(int i=0; i # Definition for singly-linked list. # 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: #create a dummy head dummy = ListNode(0) dummy.next = head #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 the new head return dummy.next//Given a linked list, remove the n-th node from the end of list and return its head. /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { let slow = head; let fast = head; 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; return head; };/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { // Base case if (head == NULL) { return NULL; } // Two pass algorithm // 1. Calculate the length of the list int length = 0; ListNode* curr = head; while (curr != NULL) { length++; curr = curr->next; } // 2. Remove the nth node from the end int count = 0; curr = head; 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 head = head->next; } else { prev->next = curr->next; } delete curr; return head; } };/** * Definition for singly-linked list. * 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); dummy.next = head; //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; } }