19. Remove Nth Node From End of List

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
// Creating a dummy node to simplify the removal of head
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode slow = dummy;
        ListNode fast = dummy;
        
        // 1. Move fast n+1 step forward so that slow is in front of the node being deleted
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        
        // 2. Move fast to the end, and slow to the node before the deleted one
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        // 3. Remove the nth node from the end (slow.next points to it)
slow.next = slow.next.next;
        
        // Returning a new head (dummy.next could have changed if the head was deleted)
        return dummy.next;
    }
}
        

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        count = 0
        curr = head
        dummy = curr

        while curr:
            count += 1
            curr = curr.next
        # if count == 1 and n == 1:
        #     return None

        if count == n:
            head = head.next

        remove = count - n
        count = 0
        while dummy:
            count +=1
            if count == remove:
                dummy.next = dummy.next.next
                break
            dummy = dummy.next

        return head
        

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* temp=head;
    int count=0;
    while(temp!=NULL){
        temp=temp->next;
        count=count+1;

    }
     if (count == n) {
        struct ListNode* newHead = head->next;
        free(head);
        return newHead;
    }
    struct ListNode* tempa=head;
    for(int i=0;i<count-n-1;i++){
        tempa=tempa->next;

    }
    struct ListNode* tem=tempa->next;
     tempa->next=tempa->next->next;
    free(tem);
   
   return head;
}
        

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode fast = dummy;
        ListNode slow = dummy;

        // Move fast pointer n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // Move both pointers until fast reaches the end
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // Remove the nth node from the end
        slow.next = slow.next.next;

        return dummy.next;

    }
}
        

var removeNthFromEnd = function(head, n) {
    let fast = head, slow = head
    for (let i = 0; i < n; i++) fast = fast.next
    if (!fast) return head.next
    while (fast.next) fast = fast.next, slow = slow.next
    slow.next = slow.next.next
    return head
};
        

// We assume ListNode is provided by the environment and should not be redefined.

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    // Create a dummy node to simplify edge cases
    const dummy = new ListNode(0);
    dummy.next = head;
    let first: ListNode | null = dummy;
    let second: ListNode | null = dummy;

    // Move the first pointer n+1 steps ahead
    for (let i = 0; i <= n; i++) {
        first = first?.next ?? null;
    }

    // Move both pointers until the first pointer reaches the end
    while (first !== null) {
        first = first.next;
        second = second?.next ?? null;
    }

    // Remove the nth node from the end
    second!.next = second?.next?.next ?? null;

    // Return the new head of the list
    return dummy.next;
}
        

class Solution {

    /**
     * @param ListNode $head
     * @param Integer $n
     * @return ListNode
     */
    function removeNthFromEnd($head, $n) {
        $dummy = new ListNode(0, $head);
        $first = $dummy;
        $second = $dummy;

        for ($i = 0; $i <= $n; $i++) {
            $first = $first->next;
        }
        
        while ($first !== null) {
            $first = $first->next;
            $second = $second->next;
        }
        $second->next = $second->next->next;

        return $dummy->next;        
    }
}
        

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let node = ListNode(0)
        node.next = head
        
        var prev: ListNode? = node
        var post: ListNode? = node
        
        for _ in 0..<n {
            guard let next = post?.next else { continue }
            post = next
        }
        
        while let postNext = post?.next, let prevNext = prev?.next {
            prev = prevNext
            post = postNext
        }
        
        prev!.next = prev!.next!.next
        
        return node.next
    }
}
        

class Solution {
    fun removeNthFromEnd(head: ListNode, n: Int): ListNode? {
        head0.next = head
        var node: ListNode? = head0
        var steps = getNodeCount(head0) - n
        while (steps > 1) {
            steps--
            node = node?.next
        }
        node?.next = node?.next?.next
        return head0.next
    }

    private fun getNodeCount(head: ListNode): Int {
        var count = 0
        var node: ListNode? = head
        while (node != null) {
            node = node.next
            count++
        }
        return count
    }

    companion object {
        val head0 = ListNode(0)
    }
}
        

class Solution {
ListNode? removeNthFromEnd(ListNode? head, int n) {
  final dummy = ListNode(0, head);
  ListNode? left = dummy;
  ListNode? right = head;

  while(n > 0 && right != null) {
    right = right.next;
    n--;
  }
  while(right != null) {
    right = right.next;
    left = left?.next;
  }
  left?.next = left.next?.next;
  return dummy.next;
}
}
        

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // Создаем фиктивный узел перед головным узлом
    dummy := &ListNode{0, head}
    slow, fast := dummy, dummy

    // Перемещаем fast на n+1 шаг вперед
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }

    // Двигаем slow и fast одновременно
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }

    // Удаляем узел, на который указывает slow.Next
    slow.Next = slow.Next.Next

    // Возвращаем обновленный список, пропуская фиктивный узел
    return dummy.Next
}