删除列表的倒数第n个结点

可以使用双指针的方法来删除列表的倒数第n个结点。

首先让快指针 `p` 先移动 n 步，然后让慢指针 `q` 和快指针 `p` 同时移动，直到快指针 `p` 到达链表末尾。此时慢指针 `q` 指向的结点就是要删除的结点的前一个结点。

具体实现可以参考下面的 Python 代码：

def removeNthFromEnd(head, n):
    dummy = ListNode(0)  # 添加虚拟头结点
    dummy.next = head

    p = q = dummy
    for i in range(n):
        p = p.next

    while p.next:
        p = p.next
        q = q.next

    q.next = q.next.next  # 删除结点

    return dummy.next

这里假设链表的头结点为 `head`，要删除的结点为倒数第 `n` 个结点。其中 `ListNode` 是链表节点的定义。

相关问题

python删除列表的倒数第n个结点

可以使用双指针来实现删除列表的倒数第n个结点。

具体做法是，使用两个指针p和q，先将q指针向后移动n个位置，然后同时移动p和q指针，直到q指针到达链表末尾，此时p指针就指向了倒数第n个结点的前一个结点。最后通过p指针删除倒数第n个结点即可。

以下是示例代码：

def removeNthFromEnd(head, n):
    p, q = head, head
    for i in range(n):
        q = q.next
    if not q:
        return head.next
    while q.next:
        p = p.next
        q = q.next
    p.next = p.next.next
    return head

其中，head为链表的头节点，n为要删除的倒数第n个结点的位置。注意需要特判删除头节点的情况。

删除列表的倒数第n个结点并返回列表

下面是一种可能的实现方式：

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    # 创建虚拟头结点
    dummy = ListNode(0)
    dummy.next = head

    # 计算链表长度
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next

    # 找到要删除的结点的前一个结点
    curr = dummy
    for i in range(length - n):
        curr = curr.next

    # 删除结点
    curr.next = curr.next.next

    # 返回头结点
    return dummy.next

该函数接收一个链表头结点 `head` 和一个正整数 `n`，表示要删除倒数第 `n` 个结点。首先创建一个虚拟头结点 `dummy`，将其指向原链表的头结点。然后遍历一遍链表，计算出链表的长度 `length`。接下来再次遍历链表，找到要删除的结点的前一个结点。最后将该结点的 `next` 指针指向下下个结点即可。

注意，这里的删除操作是指将要删除结点的前一个结点的 `next` 指针指向下下个结点，而不是直接删除要删除的结点。这是因为单向链表无法直接找到要删除结点的前一个结点，需要从头结点开始遍历，时间复杂度为 $O(n)$，不如直接遍历一遍链表计算出要删除的结点的位置，时间复杂度也为 $O(n)$。