打卡群2刷题总结1006—— 删除链表的倒数第N个节点

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。

进阶：
你能尝试使用一趟扫描实现吗？

# 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: ListNode, n: int) -> ListNode:
        # 增加空的头结点，使得逻辑一致
        node = ListNode(val=0, next=head)
        head = node
        
        # 找到第n-1个节点
        count = 0
        p = head
        while count < n:
            count += 1
            p = p.next
        
        # 找到倒数第n+1个节点
        q = head
        while p.next:
            p = p.next
            q = q.next
        
        # 删除倒数第n个节点
        r = q.next
        q.next = q.next.next
        del r
        return head.next