👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python欢迎加入社区:
码上找工作http://t.csdnimg.cn/Q59WX
作者专栏每日更新:LeetCode解锁1000题: 打怪升级之旅https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化:企业实战案例https://blog.csdn.net/cciehl/category_12615648.html
备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个链表,删除链表的倒数第 n
个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n
保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
解题思路
解决这个问题的关键是找到倒数第 n+1
个节点。我们可以使用两个指针 first
和 second
同时对链表进行遍历,并且 first
比 second
超前 n+1
步。当 first
遍历到链表末尾时,second
将指向倒数第 n+1
个节点。然后我们就可以调整 second
的 next
指针来删除倒数第 n
个节点。
代码实现
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
first = dummy
second = dummy
# 移动 first,使得 first 和 second 之间相隔 n+1 个节点
for _ in range(n + 1):
first = first.next
# 同时移动 first 和 second,直到 first 指向链表末尾
while first is not None:
first = first.next
second = second.next
# 删除倒数第 n 个节点
second.next = second.next.next
return dummy.next
算法分析
- 时间复杂度:O(L),其中 L 是链表的长度。算法对链表进行了一次遍历。
- 空间复杂度:O(1),只用了常数级别的额外空间。
算法图解
初始状态
- 假设链表为
1 -> 2 -> 3 -> 4 -> 5
,n = 2
,目标是删除倒数第二个节点,即节点4
。 - 我们引入一个哑节点(dummy node)作为链表的新头节点,这样可以方便地处理边界情况,比如删除头节点。
表示链表的表格如下:
添加双指针
- 设置两个指针
first
和second
,初始时都指向哑节点。
移动 first
指针
- 将
first
指针向前移动n + 1
步,使得first
和second
之间相隔n
个节点。
同时移动 first
和 second
指针
- 同时移动
first
和second
指针,直到first
指向链表末尾的空节点。此时,second
将指向倒数第n + 1
个节点。
删除倒数第 N 个节点
- 调整
second
的next
指针,使其指向倒数第n
个节点的下一个节点,从而删除倒数第n
个节点。
结果
删除节点 4
后的链表为:1 -> 2 -> 3 -> 5
。
通过这种方法,我们只需要一趟扫描就能找到倒数第 n
个节点的位置,并进行删除操作,达到高效解决问题的目的。
结论
通过使用双指针的方法,我们可以高效地解决删除链表倒数第 N 个节点的问题,这个技巧在链表问题中非常实用,值得掌握。