# 19\. Remove Nth Node From End of List




\- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \- \-


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

"""
edge case:
- Null linked list // no such
- removal target as 0th
- removal target as 1th
"""

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next
            
        prev = None
        cur = head
        m = length - n  # count from head, 1-indexing
        for _ in range(m):
            prev = cur
            cur = cur.next
        
        if prev is None:
            if cur.next is None:
                return None
            else:
                return cur.next
        else:
            prev.next = cur.next
            return head

"""
Best

https://leetcode.com/media/original_images/19_Remove_nth_node_from_end_of_listB.png

Approach 2: One pass algorithm

Algorithm

The above algorithm could be optimized to one pass. Instead of one pointer, we could use two pointers. The first pointer advances the list by n+1n+1n+1 steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are exactly separated by nnn nodes apart. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the nnnth node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node's next next node.
"""
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        p1, p2 = head, head
        for i in range(n):
            p2 = p2.next
        if not p2:
            return head.next
        while p2.next:
            p1 = p1.next
            p2 = p2.next
        p1.next = p1.next.next
        return head
    
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        li = []
        cur = head
        while cur:
            li.append(cur)
            cur = cur.next
            
        pos = len(li) - n  # 0-indexing # pos ofcur = head
        while cur:
            length += 1
            cur = cur.next
        
        if pos == 0:
            return head.next
        else:
            li[pos - 1].next = li[pos].next
            return head