删除链表倒数第n个节点 力扣 包括输入和输出

删除链表倒数第 n 个节点是一个常见的链表操作题目，在数据结构中尤其实用。给定一个单向链表和一个整数 n，你需要从链表的末尾开始往前数，找到第 n 个节点，并将其从链表中移除。链表的输入通常是一个指向头节点的指针，而输出则是更新后的链表。

**步骤描述：**
1. 初始化两个指针，`p` 和 `q`，分别表示当前节点和前一个节点。初始时，`p` 指向头节点，`q` 点向 null。
2. 当 `p` 遍历到链表的第 n 个节点时，即 `p` 走了 n 步，`q` 则走了 n-1 步。此时，`q` 就是指向倒数第 n 个节点的前一个节点。
3. 如果 `p` 或者 `q` 未到达链表尾部，则将 `q` 的 next 指针指向 `p` 的下一个节点，实现了对倒数第 n 个节点的删除。
4. 返回头节点作为结果链表。

**Python 示例：**

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    p = head
    q = None
    
    # 先让p向前走n步
    for _ in range(n):
        if not p:
            return head  # 如果n大于链表长度，则直接返回头节点
        p = p.next
        
    # 保持p在n位置，然后同时移动p和q直到p到达尾部
    while p.next:
        p = p.next
        q = q.next
        
    # 删除倒数第n个节点
    if q:
        q.next = q.next.next
        
    return head