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

Constraints:

• The number of nodes in the list is sz.

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

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]

💡 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

class Solution {
    /**  
     * @time  : O(n)
     * @space : O(1)
     */
    
    public ListNode removeNthFromEnd(ListNode head, int n) {
        /* base case */
        if(head.next == null && n == 1) return null;
        
        ListNode slowP = head, fastP = head;
        
        /* Move fast-pointer so that the gap between two pointers is n nodes apart */
        for (int i=0 ; i<n ; i++) fastP = fastP.next;
        
        /* nth node from the end points to HEAD */
        if(fastP == null) return head.next;
            
        /* Move fast-pointer to the end, maintaining the gap */
        while (fastP.next != null) {
            slowP = slowP.next;
            fastP = fastP.next;
        }
        
        slowP.next = slowP.next.next;
        return head;
    }
}