- 难度: 中等
- 考察: 链表
- 来源: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
- 题解: https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0019-Remove-Nth-Node-From-End-of-List/Article/0019-Remove-Nth-Node-From-End-of-List.md
- 题解: https://github.com/azl397985856/leetcode/blob/master/problems/19.removeNthNodeFromEndofList.md
题目
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
1 | 给定一个链表: 1->2->3->4->5, 和 n = 2. |
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
思路
采取双重遍历肯定是可以解决问题的,但题目要求我们一次遍历解决问题,那我们的思路得发散一下。
我们可以设想假设设定了双指针p
和q
的话,当q
指向末尾的NULL
,p
与q
之间相隔的元素个数为n
时,那么删除掉p
的下一个指针就完成了要求。
- 设置虚拟节点
dummyHead
指向head
- 设定双指针
p
和q
,初始都指向虚拟节点dummyHead
- 移动
q
,直到p
与q
之间相隔的元素个数为n
- 同时移动
p
与q
,直到q
指向的为NULL
- 将
p
的下一个节点指向下下个节点
关键点
- 双指针
复杂度
- 时间复杂度:O(N)
- 空间复杂度:O(1)
代码
1 | /** |