LeetCode19: 删除链表的倒数第n个结点

  • A+
所属分类:算法与数据结构
LeetCode19: 删除链表的倒数第n个结点

article_img

题目描述

如题

解题思路

方案一

第一次遍历,得到链表长度,再次遍历找到删除结点前一个结点,删除目标结点即可。时间复杂度O(n),但需遍历两次。空间复杂度O(1)。注意,删除结点要用到prev结点,如果要删除头结点,则没有prev结点,需要特殊判断和处理。或者使用哨兵结点,简化代码。

Java代码

方案二

使用两个指针,一前一后,相隔n个结点。同时移动,直到前一个结点到达链表的尾部。然后另一个指针处理删除的结点。此方法只需遍历一次。时间复杂度O(n),空间复杂度O(1)。

 

LTXU

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: