DEV Community
·
Leetcode - 19. 删除链表倒数第N个节点
💡
原文英文，约400词，阅读约需2分钟。
📝
内容提要
给定一个单链表，使用双指针技术删除倒数第n个节点。首先创建一个指向头节点的虚拟节点，初始化左指针指向虚拟节点，右指针指向头节点，并让右指针向前移动n步。然后同时移动两个指针，直到右指针到达链表末尾。此时，左指针的下一个节点即为要删除的节点，更新左指针的下一个节点为其下下个节点，最后返回虚拟节点的下一个节点作为新头。
🎯
关键要点
- 给定一个单链表，任务是删除倒数第n个节点并返回更新后的头节点。
- 使用双指针技术高效地解决问题。
- 创建一个虚拟节点指向头节点，以简化删除第一个节点等边界情况。
- 初始化两个指针：左指针指向虚拟节点，右指针指向头节点。
- 右指针向前移动n步，确保左指针和右指针之间的间隔为n个节点。
- 同时移动两个指针，直到右指针到达链表末尾。
- 此时，左指针的下一个节点即为要删除的节点，更新左指针的下一个节点为其下下个节点。
- 返回虚拟节点的下一个节点作为新头。
- 时间复杂度为O(L)，L为链表中的节点数。
- 空间复杂度为O(1)，除了几个指针外不使用额外空间。
❓
延伸问答
如何使用双指针技术删除链表中的倒数第n个节点？
首先创建一个虚拟节点指向头节点，初始化左指针指向虚拟节点，右指针指向头节点。右指针向前移动n步，然后同时移动两个指针，直到右指针到达链表末尾。此时，左指针的下一个节点即为要删除的节点，更新左指针的下一个节点为其下下个节点。
删除链表倒数第n个节点的时间复杂度和空间复杂度是多少？
时间复杂度为O(L)，空间复杂度为O(1)，其中L为链表中的节点数。
为什么要使用虚拟节点来删除链表中的节点？
使用虚拟节点可以简化边界情况的处理，例如删除链表的第一个节点。
在删除节点的过程中，如何确保左指针和右指针之间的间隔为n个节点？
在初始化时，右指针向前移动n步，这样左指针和右指针之间的间隔就保持为n个节点。
如何返回更新后的链表头节点？
在删除节点后，返回虚拟节点的下一个节点作为新的头节点。
在实现中，如何处理链表为空或只有一个节点的情况？
通过使用虚拟节点，可以有效处理链表为空或只有一个节点的情况，避免复杂的边界条件判断。
➡️
