👤作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区作者专栏每日更新：
备注说明：方便大家阅读，统一使用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 个节点的问题，这个技巧在链表问题中非常实用，值得掌握。
欢迎关注微信公众号 数据分析螺丝钉
