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
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;
    }
}