Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

                    Input: head = [1,2,3,4,5], n = 2
                    Output: [1,2,3,5]

Example 2:

                   Input: head = [1], n = 1
                   Output: []

Example 3:

                   Input: head = [1,2], n = 1
                   Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Solution

Let l be the length of the Linked List. To get to the index of the nth node from end, we need to traverse till l-n from the beginning. While traversing, we will have two pointers, a prev pointer that will store the previous node, and the current pointer that will store the current node. After reaching the nth node index, we will have the prev pointer point to the next of the current pointer and the nth node will be removed.

Let us take an example. We have linked list [1,2,3] and n = 2 . Our two pointers will start at head. At first iteration the current will go to the next node and our prev pointer will stay at the head. Since it is the node to be deleted (l-n),we come out of the loop and make prev.next = current.next , hence deleting the node.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:

        # to get the length of linked list
        l_pointer = head
        l = 0
        while(l_pointer is not None):
            l += 1
            l_pointer = l_pointer.next
        
        # getting nth node index and creating two pointers 
        l = l-n
        prev = head
        current = head

        # if the list has only one element
        if l == 0:
            current = head.next 
            return current

        else:
            while(l>0):
                prev = current
                current = current.next
                l = l-1
            prev.next = current.next
            return head

Time complexity: O(N)

Space Complexity: O(1), since we are using constant space.