19. 删除链表的倒数第 n 个结点
时间: 2023-12-23 14:01:11 浏览: 90
19删除链表的倒数第 N 个结点.zip
删除链表的倒数第 n 个结点可以通过双指针法来实现。首先定义一个虚拟头结点dummy,然后设置两个指针slow和fast,初始时都指向dummy。接着将fast指针向前移动n+1步,然后slow和fast指针一起向前移动,直到fast指针指向空或者到达链表末尾。此时slow指针所指向的结点就是要删除的倒数第n个结点的前一个结点。
然后,我们可以进行删除操作,将slow指针所指结点的next指针指向下下个结点,从而删除倒数第n个结点。最后返回dummy.next即可得到删除倒数第n个结点后的链表。
但是需要注意的是,当要删除的是头结点时,需要单独处理,可以设置一个哨兵结点来避免头结点的特殊情况。
通过双指针法,可以以O(n)的时间复杂度和O(1)的空间复杂度完成删除链表的倒数第n个结点的操作。这种方法的关键在于利用快慢指针的思想,使得在一次遍历中即可完成删除操作,避免了遍历两次链表或使用额外的空间。
阅读全文