19. 删除链表的倒数第 N 个结点

**删除链表的倒数第 N 个结点**

在链表中，删除一个结点通常涉及到修改指向该结点的前驱结点的 next 指针。但是，如果我们要删除链表的倒数第 N 个结点呢？这种情况下，我们需要先找到倒数第 N 个结点，然后再进行删除操作。

**思路**

1. 首先，我们需要找到链表中倒数第 N 个结点。我们可以使用一个指针从链表头部开始向后移动 N 次，这样就能找到倒数第 N 个结点。
2. 一旦我们找到了倒数第 N 个结点，我们就可以删除它了。但是，需要注意的是，如果链表中只有一个结点，那么删除这个结点会导致链表变成空链表。

**代码示例**

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef delete_nth_from_end(head, n):
 """
 Deletes the nth node from the end of a linked list.

 Args:
 head (ListNode): The head of the linked list.
 n (int): The position of the node to be deleted from the end.

 Returns:
 ListNode: The head of the modified linked list.
 """

 # Create a dummy node to simplify some corner cases dummy = ListNode(0)
 dummy.next = head # Initialize two pointers, both pointing at the dummy node first = dummy second = dummy # Move the second pointer n steps ahead for _ in range(n):
 if not second.next:
 return None # If there are less than n nodes, return None second = second.next # Move both pointers one step at a time until the second pointer reaches the end while second.next:
 first = first.next second = second.next # Delete the nth node from the end by changing the next pointer of the previous node first.next = first.next.next return dummy.next# Example usage:
if __name__ == "__main__":
 # Create a sample linked list:1 ->2 ->3 ->4 ->5 head = ListNode(1)
 head.next = ListNode(2)
 head.next.next = ListNode(3)
 head.next.next.next = ListNode(4)
 head.next.next.next.next = ListNode(5)

 # Delete the2nd node from the end (i.e., node with value3)
 new_head = delete_nth_from_end(head,2)

 # Print the modified linked list while new_head:
 print(new_head.val, end=" -> " if new_head.next else "
")
 new_head = new_head.next

**注释**

* `delete_nth_from_end` 函数的作用是删除链表中倒数第 N 个结点。
* 在函数内部，我们首先创建一个 dummy 结点来简化一些边界情况（如链表只有一个结点）。
* 然后，我们使用两个指针，分别称为 `first` 和 `second`，从链表头部开始向后移动 N 次。`second` 指针用于找到倒数第 N 个结点。
* 一旦我们找到了倒数第 N 个结点，我们就可以删除它了。但是，我们需要注意，如果链表中只有一个结点，那么删除这个结点会导致链表变成空链表。
* 最后，我们返回 `dummy.next` 作为修改后的链表头部。

**总结**

删除链表的倒数第 N 个结点涉及到找到倒数第 N 个结点，然后再进行删除操作。我们可以使用两个指针来实现这一点，分别从链表头部开始向后移动 N 次和一致移动直到第二个指针达到链表尾部。最后，我们需要注意一些边界情况，如链表只有一个结点。