给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1
输出:[]
示例 3:
输入:head = [1,2], n = 1
输出:[1]
进阶:你能尝试使用一趟扫描实现吗?
快慢指针
为什么要用dummy哑结点?
一般来说,链表题中涉及到删除、交换顺序等,会使用到dummy节点
不使用dummy节点会怎样?
不使用的话,题目要求返回链表的头结点。因此我们可以选择返回head。但是,我们需要考虑一个边界问题,如果要求删除链表的头结点呢?对于这种特殊情况,如果不使用dummy节点的话就比较复杂了。由于我们在删除操作的时候,是希望找到【想删除节点】的前一个节点。如果想删除的节点正好是第一个,那怎么办?要么特殊处理,要么设置一个新节点——dummy节点,把新节点指向头结点,这样头结点就也有前一个节点了——即dummy节点,这样删除操作就不需要对头结点进行特殊判断了。
def test(head,n):
"""
双指针,让一个指针(fast)先跑n步,后面每次两个指针都往后走一步,
直到(循环)快指针走到末尾。此时慢指针(slow)就停在倒数第N个节点的前一个节点。
:param head:
:param n:
:return:
"""
left=ListNode()
right=ListNode()
dummy=ListNode()
# step1: 快指针先走n步
for i in range(n):
right=right.next
# step2: 快慢指针同时走,直到fast指针到达尾部节点,此时slow到达倒数第N个节点的前一个节点
while right.next:
left=left.next
right=right.next
# step3: 删除节点,并重新连接
left.next=left.next.next
return dummy.next
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/123158.html