[Leetcode]19. Remove Nth Node From End of List

📄 Description

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]

🔨 My Solution

• get the size of the linked list to caculate times for swifting the pointer to find the delete node.
• find the node which is node.next==delete_node
• deleting the node is different depends on the position of the node.
  1. deleting the head node
  2. deleting the last node

💻 My Submission

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # get the size of the linked list
        cnt_ptr=head
        cnt=1
        while cnt_ptr.next:
            cnt_ptr=cnt_ptr.next
            cnt+=1
        
        # find the node which is node.next==delete_node
        delete_ptr=head
        i=0
        
        while i<cnt-n-1:
            delete_ptr=delete_ptr.next
            i+=1
        
        # if delete node is the head node
        if n==cnt:
            head=delete_ptr.next
        # elif delete node is the last node
        elif n==1:
            delete_ptr.next=None
        else:
            delete_ptr.next=delete_ptr.next.next
        
        delete_ptr=None
        
        return head

🔎 Complexity

Runtine: 58 ms
Memory: 14 MB

💊 Better Solution

• using two pointers: can cover more situation at a same condition.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        temp = head
        c = 0
        while temp:     #Find the length of the linked list
            c+=1
            temp = temp.next
        a = c-n+1       #Calculate the node to be removed
        i = 1
        temp2 = head
        prev = None
        while i < a:         #Traverse till the node to be removed
            i+=1
            prev = temp2     #Prev pointer to point the previous node of the deletion node
            temp2 = temp2.next
        if temp2==head:
            return head.next
        prev.next = temp2.next    #Link the previous node to the next of the deletion node
        return head

References
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
https://leetcode.com/problems/remove-nth-node-from-end-of-list/discuss/1834999/Python3-Runtime%3A-16-ms-faster-than-99.82-or-Memory%3A-13.7-MB-less-than-98.65