Remove Nth Node From End Of List

Question

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]

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

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

Solution

To find nth node from the end, we need to apply Fast and Slow pointers concept.

For example if we want to remove the 2nd node from the end:

We want to start from the start with our fast and slow pointers separated by 2 jumps. For example:

And then we keep moving to the end node:

Now the node we want to remove should be slow.next.

Edge cases

In the case we remove the root node, for example in this case we're removing the 5th node

That means when creating fast and slow pointers, fast will be at the end (null):

So we can conclude that: if for whatever reason fast is null, that means we want to remove the first node

Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class App:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if head is None: raise Exception("Head should not be null")
        
        slow, fast = head, head 
        
        for _ in range(0, n):
            if not fast: raise Exception("N is more than size")
            fast = fast.next
        
        if not fast: # Reached to the end (n == size) -> remove the root
            return head.next
        
        while fast.next:
            slow = slow.next
            fast = fast.next
        
        # Next node is what needed to be removed
        self.removeNext(slow)
        
        return head

    def removeNext(self, node: ListNode) -> None:
        node.next = node.next.next
        

Time complexity: $O(n)$
Space complexity: $O(1)$