0019. Remove Nth Node From End of List

Medium | Linked List + Two Pointer | 12 ms (98.94%), 13.3 MB (72.36%)

❓ Problem Statement

Source: LeetCode - Remove Nth Node From End of List GitHub: Solution / Performance

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

✍🏻 Constraints & Example

💡 Ideas

Use a hash table to record each node's location needs O(n). Instead, we could manipulate two pointers to create a gap between two pointers to find the target node, and that only required O(1) space complexity.

1. Move the fast-pointer forward to create n gaps apart from the slow-pointer

2. If the fast-point now points to null, it means the first node is the one to be removed

3. Move forward the fast-pointer and slow-pointer together until the next node of the fast-pointer is null

4. Now, the next node of the slow-pointer is the one that needs to be removed. So then break the link by slowP.next = slowP.next.next and return the head

🤖 Python3

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # (base case)
        if not head.next and n == 1: return None
        
        # ==================================================
        #  Linked List + Two Pointer                       =
        # ==================================================
        # time  : O(n), one pass
        # space : O(1)
        
        slowP, fastP = head, head
        
        # move fast-pointer to keep the gap(n) apart from slow-pointer
        for i in range(n): fastP = fastP.next
        
        # n == length of the linked list
        if not fastP: return head.next
        
        # move fast-pointer to the end, maintaining the gap
        while fastP.next: slowP, fastP = slowP.next, fastP.next
            
        slowP.next = slowP.next.next
        return head
        
        '''
        # ==================================================
        #  Linked List + Hash Table                        =
        # ==================================================
        # time  : O(n), one pass
        # space : O(n)
        
        ret = head
        
        index = 0
        table = dict()
        while head:
            table[index] = head
            head = head.next
            index += 1
        
        if n == index: return ret.next
        
        # find the node before the one that needs to be removed
        node = table[index - n - 1]
        node.next = node.next.next
        
        return ret
        '''

🤖 Java