Python3 | Beats 95% | Efficient Removal of Nth Node from the End of a Linked List
Solution no. 01\nThe first solution helps you understand the basics with simple steps. \n\n# Intuition\n\nTo determine the node to remove, which is n positions 
# Solution no. 01\nThe first solution helps you understand the basics with simple steps. \n\n# Intuition\n\nTo determine the node to remove, which is n positions from the end, we need to figure out how many positions we should move from the front to reach the desired node. By counting the total number of nodes in the linked list, we gain this insight and can then adjust the connections accordingly to remove the targeted node from the end.\n\n# Approach\n1. Count the total number of nodes in the linked list by traversing it with a curr pointer.\n1. Calculate the position to move from the front to reach the node n positions from the end.\n1. Reset the count and curr to traverse the list again.\n1. If the node to be removed is the first node, return head.next.\n1. Traverse the list while keeping track of the count.\n1. When the count matches the calculated position before the node to be removed, update the connection to skip the node.\n1. Exit the loop after performing the removal.\n1. Return the updated head.\n\n# Complexity\n- Time complexity:\nWe traverse the linked list twice, so the time complexity is O(n), where n is the number of nodes in the list.\n\n- Space complexity:\nWe only use a few variables, so the space complexity is O(1).\n\n# Code\n```\nclass Solution:\n    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n        count = 0\n        curr = head\n        while curr:\n            count += 1\n            curr = curr.next\n\n        check = count - n - 1\n        count = 0\n        curr = head\n\n        # Removing the first node\n        if check == -1:  \n            return head.next\n\n        while curr:\n            if count == check:\n                curr.next = curr.next.next\n                # As the removal is done, Exit the loop\n                break  \n            curr = curr.next\n            count += 1\n\n        return head\n\n```\n\n\n---\n\n# Solution no. 02\n\n# Intuition\nIn our first approach we counted the total number of nodes in the linked list and then identify the n-th node from the end by its position from the beginning. While this counting approach could work, it involves traversing the list twice: once to count the nodes and once to find the node to remove. This double traversal can be inefficient, especially for large lists.\n\nA more efficient approach comes from recognizing that we don\'t really need to know the total number of nodes in the list to solve this problem. Instead, we can utilize two pointers to maintain a specific gap between them as they traverse the list. This gap will be the key to identifying the n-th node from the end.\n\n# Approach\n1. We\'ll use two pointers, first and second, initialized to a dummy node at the beginning of the linked list. The goal is to maintain a gap of n+1 nodes between the two pointers as we traverse the list.\n\n1. Move the first pointer n+1 steps ahead, creating a gap of n nodes between first and second.\n\n1. Now, move both first and second pointers one step at a time until the first pointer reaches the end of the list. This ensures that the gap between the two pointers remains constant at n nodes.\n\n1. When first reaches the end, the second pointer will be pointing to the node right before the node we want to remove (n-th node from the end).\n\n1. Update the second.next pointer to skip the n-th node, effectively removing it from the list.\n\n# Complexity\n- Time complexity:\n The solution involves a single pass through the linked list, so the time complexity is **O(N)**, where N is the number of nodes in the linked list.\n\n- Space complexity:\nWe are using a constant amount of extra space to store the dummy, first, and second pointers, so the space complexity is **O(1)**.\n\n# Code\n```\nclass Solution:\n    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n        dummy = ListNode(0)\n        dummy.next = head\n        \n        first = dummy\n        second = dummy\n        \n        # Advance first pointer so that the gap between first and second is n+1 nodes apart\n        for i in range(n+1):\n            first = first.next\n        \n        # Move first to the end, maintaining the gap\n        while first:\n            first = first.next\n            second = second.next\n        \n        # Remove the nth node from the end\n        second.next = second.next.next\n        \n        return dummy.next \n\n```\n\n
['Linked List', 'Two Pointers', 'Python', 'Python3']