Removing Nth Node from End of Linked List | | Slow-Fast Approach | |  100% beats | | 💯💯
\n\n# Intuition\nTo remove the Nth node from the end of the linked list, we can first traverse the list to find its length. Then, we calculate the position of t
![image.png](https://assets.leetcode.com/users/images/9f7adde3-6284-4084-b7e1-bfcd650c071a_1709432455.1489832.png)\n\n# Intuition\nTo remove the Nth node from the end of the linked list, we can first traverse the list to find its length. Then, we calculate the position of the node to be removed from the beginning by subtracting N from the length. After that, we traverse the list again until we reach the node just before the one to be removed, update the pointers accordingly, and delete the node.\n\n# Approach\n1. Traverse the linked list to find its length.\n2. Calculate the position of the node to be removed from the beginning by subtracting N from the length.\n3. Traverse the list again until we reach the node just before the one to be removed.\n4. Update the pointers accordingly to remove the node.\n5. Delete the removed node.\n\n# Complexity\n- Time complexity: O(n), where n is the number of nodes in the linked list. We traverse the list twice.\n- Space complexity: O(1), as we are using only a constant amount of extra space.\n\n# Code\n```java []\n/*\n * Definition for singly-linked list.\n * class ListNode {\n *     int val;\n *     ListNode next;\n *     ListNode() {}\n *     ListNode(int val) { this.val = val; }\n *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }\n * }\n */\nclass Solution {\n    public ListNode removeNthFromEnd(ListNode head, int n) {\n        int len = 0;\n        ListNode temp = head;\n        \n        // Step 1: Traverse the linked list to find its length\n        while(temp != null) {\n            len++;\n            temp = temp.next;\n        }\n        \n        // Reset temp to the head of the list\n        temp = head;\n        ListNode prev = null;\n        int pos = len - n;\n        \n        // Special case: If the node to be removed is the head itself\n        if(pos == 0) return head.next;\n        \n        // Step 2: Traverse the list again to reach the node just before the one to be removed\n        for(int i = 0; i < pos; i++) {\n            prev = temp;\n            temp = temp.next;\n        }\n        \n        // Step 3: Update the pointers to remove the node\n        prev.next = temp.next;\n        \n        // Step 4: Delete the removed node\n        temp = null;\n        \n        return head;\n    }\n}\n\n```\n```c++ []\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    ListNode* removeNthFromEnd(ListNode* head, int n) {\n        int len = 0;\n        ListNode *temp = head;\n        \n        // Step 1: Traverse the linked list to find its length\n        while(temp != nullptr) {\n            len++;\n            temp = temp->next;\n        }\n        \n        // Reset temp to the head of the list\n        temp = head;\n        ListNode* prev;\n        int pos = len - n;\n        \n        // Special case: If the node to be removed is the head itself\n        if(pos == 0) return head->next;\n        \n        // Step 2: Traverse the list again to reach the node just before the one to be removed\n        for(int i = 0; i < pos; i++) {\n            prev = temp;\n            temp = temp->next;\n        }\n        \n        // Step 3: Update the pointers to remove the node\n        prev->next = temp->next;\n        \n        // Step 4: Delete the removed node\n        delete temp;\n        \n        return head;   \n    }\n};\n```\n\n# Dry Run\nLet\'s dry run the provided test case `[1,2,3,4,5]`:\n\n1. Initial State: `head` points to the first node `[1]`.\n\n2. We traverse the list to find its length. The length is 5.\n\n3. We calculate the position of the node to be removed from the beginning: `pos = 5 - 2 = 3`.\n\n4. We traverse the list again to reach the node just before the one to be removed.\n\n5. After traversal, `prev` points to node `[3]` and `temp` points to node `[4]`.\n\n6. We update the pointers to remove node `[4]` from the list.\n\n7. The list becomes `[1,2,3,5]`, and the node `[4]` is deleted.\n\n8. The final state of the list is returned.\n\n\n\n\n\n# One - Pass Solution (Slow - Fast Approach)\n\n1. **Initialization**: Initialize two pointers, `slow` and `fast`, both pointing to the head of the linked list.\n\n2. **Move `fast` pointer**: Move the `fast` pointer `n` steps ahead of the `slow` pointer. This effectively creates a gap of `n` nodes between the `slow` and `fast` pointers.\n\n3. **Handle special case**: If `fast` pointer becomes `NULL` after moving `n` steps, it means the node to be deleted is the head node. So, simply move the head to the next node and delete the original head.\n\n4. **Move both pointers until `fast` reaches the end**: Now, move both pointers (`slow` and `fast`) simultaneously until `fast` reaches the last node (`fast->next` becomes `NULL`). At this point, `slow` will be pointing to the node just before the node to be deleted.\n\n5. **Remove the node**: Once we find the node just before the one to be deleted (`slow`), we simply skip over the node to be deleted by updating `slow->next` to `slow->next->next`. We also store the node to be deleted (`delNode`) to delete it later.\n\n6. **Delete the node**: After removing the node from the linked list, we delete it from memory to avoid memory leaks.\n\n7. **Return the head**: Finally, return the head of the modified linked list.\n\n\n# **C++**\n```cpp\nclass Solution {\npublic:\n    ListNode* removeNthFromEnd(ListNode* head, int n) {\n        ListNode *slow = head;\n        ListNode *fast = head;\n\n        // Move fast pointer \'n\' steps ahead\n        for(int i=0; i<n; i++){\n            fast = fast->next;\n        }\n\n        // Handle special case: deletion of head node\n        if(fast == NULL){\n            ListNode *ans = head->next;\n            delete(head);\n            return ans;\n        }\n\n        // Move both pointers until fast reaches the end\n        while(fast && fast->next){\n            slow = slow->next;\n            fast = fast->next;\n        }\n\n        // Remove the nth node from the end\n        ListNode *delNode = slow->next;\n        slow->next = slow->next->next;\n\n        // Delete the node\n        delete(delNode);\n\n        // Return the head of modified list\n        return head;\n    }\n};\n```\n\n**This algorithm has a time complexity of O(L)**, where L is the length of the linked list. This is a one-pass solution, meaning it only needs to traverse the linked list once to find the node to be deleted.\n\n![image.png](https://assets.leetcode.com/users/images/b37dbb9d-9c9c-4e45-8e7a-c4d6bdca1d29_1709433062.6174948.png)\n
['Linked List', 'C++', 'Java']