LeetCode上第19号问题:删除链表的倒数第N个节点
题目
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
解题思路
采取双重遍历肯定是可以解决问题的,但题目要求我们一次遍历解决问题,那我们的思路得发散一下。
我们可以设想假设设定了双指针p
和q
的话,当q
指向末尾的NULL
,p
与q
之间相隔的元素个数为n
时,那么删除掉p
的下一个指针就完成了要求。
-
设置虚拟节点
dummyHead
指向head
-
设定双指针
p
和q
,初始都指向虚拟节点dummyHead
-
移动
q
,直到p
与q
之间相隔的元素个数为n
-
同时移动
p
与q
,直到q
指向的为NULL
-
将
p
的下一个节点指向下下个节点
动画演示
动画演示GIF有点大,请稍微等待一下加载显示^_^