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有点大,请稍微等待一下加载显示^_^