19. Remove Nth Node From End Of List

19. Remove Nth Node From End of List

Medium

---

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

 

Follow up: Could you do this in one pass?

 # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
#         size = 0
#         node = head
#         while node:
#             size+=1
#             node = node.next

#         node = head
#         target_node_position = size - n 

#         # head
#         if target_node_position == 0:
#             return head.next

#         target_node_position -=1

#         # head is removed, now the rest of them
#         for i in range(target_node_position+1):
#             if i == target_node_position:
#                 node.next = node.next.next
#             node = node.next

#         return head 

         # two pointer approach
        current_node = head
        for i in range(n):
            current_node=current_node.next

        if current_node is None:
            return head.next

        node_before_remove = head

        while current_node.next is not None:
            current_node = current_node.next
            node_before_remove = node_before_remove.next


        node_before_remove.next = node_before_remove.next.next

        return head