✅ Remove Nth Node From End of List | Simple One-Pass Solution w/ Explanation
This problem is very similar to the 1721. Swapping Nodes in a Linked List (which was given in March LeetCoding Challenge 2021 as well), just that we have to rem
This problem is very similar to the **[1721. Swapping Nodes in a Linked List](https://leetcode.com/problems/swapping-nodes-in-a-linked-list/)** (which was given in *March LeetCoding Challenge 2021* as well), just that we have to **remove** the kth node from the end instead of swapping it.\n\n\n\n---\n\n\u2714\uFE0F ***Solution - I (One-Pointer, Two-Pass)***\n\nThis approach is very intuitive and easy to get. \n\n* We just iterate in the first-pass to find the length of the linked list - **`len`**.\n\n* In the next pass, iterate **`len - n - 1`** nodes from start and delete the next node (which would be *`nth`* node from end).\n\n---\n\n**C++**\n```\nListNode* removeNthFromEnd(ListNode* head, int n) {\n\tListNode* iter = head;\n\tint len = 0, i = 1;\n\twhile(iter) iter = iter -> next, len++;    // finding the length of linked list\n\tif(len == n) return head -> next;          // if head itself is to be deleted, just return head -> next\n\tfor(iter = head; i < len - n; i++) iter = iter -> next; // iterate first len-n nodes\n\titer -> next = iter -> next -> next;      // remove the nth node from the end\n\treturn head;\n}\n```\n\n---\n\n**Python**\n```\ndef removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n\tptr, length = head, 0\n\twhile ptr:\n\t\tptr, length = ptr.next, length + 1\n\tif length == n : return head.next\n\tptr = head\n\tfor i in range(1, length - n):\n\t\tptr = ptr.next\n\tptr.next = ptr.next.next\n\treturn head\n```\n\n\n***Time Complexity :*** **`O(N)`**, where, `N` is the number of nodes in the given list. \n***Space Complexity :*** **`O(1)`**, since only constant space is used.\n\n---\n---\n\n\u2714\uFE0F ***Solution (Two-Pointer, One-Pass)***\n\nWe are required to remove the nth node from the end of list. For this, we need to traverse *`N - n`* nodes from the start of the list, where *`N`* is the length of linked list. We can do this in one-pass as follows -\n\n* Let\'s assign two pointers - **`fast`** and **`slow`** to head. We will first iterate for *`n`* nodes from start using the *`fast`* pointer. \n\n* Now, between the *`fast`*  and *`slow`* pointers, **there is a gap of `n` nodes**. Now, just Iterate and increment both the pointers till `fast` reaches the last node. The gap between `fast` and `slow` is still of `n` nodes, meaning that **`slow` is nth node from the last node (which currently is `fast`)**.\n\n```\nFor eg. let the list be 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9, and n = 4.\n\n1. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null\n   ^slow               ^fast\n   |<--gap of n nodes-->|\n \n => Now traverse till fast reaches end\n \n 2. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null\n                        ^slow               ^fast\n                        |<--gap of n nodes-->|\n\t\t\t\t\t\t\n\'slow\' is at (n+1)th node from end.\nSo just delete nth node from end by assigning slow -> next as slow -> next -> next (which would remove nth node from end of list).\n```\n\n * Since we have to **delete the nth node from end of list** (And not nth from the last of list!), we just delete the next node to **`slow`** pointer and return the head.\n\n---\n\n**C++**\n```\nListNode* removeNthFromEnd(ListNode* head, int n) {\n\tListNode *fast = head, *slow = head;\n\twhile(n--) fast = fast -> next;      // iterate first n nodes using fast\n\tif(!fast) return head -> next;       // if fast is already null, it means we have to delete head itself. So, just return next of head\n\twhile(fast -> next)                  // iterate till fast reaches the last node of list\n\t\tfast = fast -> next, slow = slow -> next;            \n\tslow -> next = slow -> next -> next; // remove the nth node from last\n\treturn head;\n}\n```\n\n---\n\n**Python**\n```\ndef removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n\tfast = slow = head\n\tfor i in range(n):\n\t\tfast = fast.next\n\tif not fast: return head.next\n\twhile fast.next:\n\t\tfast, slow = fast.next, slow.next\n\tslow.next = slow.next.next\n\treturn head\n```\n\n\n\n***Time Complexity :*** **`O(N)`**, where, `N` is the number of nodes in the given list. Although, the time complexity is same as above solution, we have reduced the constant factor in it to half.\n***Space Complexity :*** **`O(1)`**, since only constant space is used.\n\n---\n\n**Note :** The Problem only asks us to **remove the node from the linked list and not delete it**. A good question to ask in an interview for this problem would be whether we just need to remove the node from linked list or completely delete it from the memory. Since it has not been stated in this problem if the node is required somewhere else later on, its better to just remove the node from linked list as asked.\n\nIf we want to delete the node altogether, then we can just free its memory and point it to NULL before returning from the function.\n\n\n---\n---\n\n*Best Runtime -*\n\n<table><tr><td><img src=https://assets.leetcode.com/users/images/6c81d074-139d-4de5-96f5-5943f62a2cca_1618736585.2373421.png /></td></tr></table>\n\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any questions or mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
['C', 'Python']