每天一算:Remove Nth Node From End of List

LeetCode上第19号问题:删除链表的倒数第N个节点

题目

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

解题思路

采取双重遍历肯定是可以解决问题的,但题目要求我们一次遍历解决问题,那我们的思路得发散一下。

我们可以设想假设设定了双指针pq的话,当q指向末尾的NULLpq之间相隔的元素个数为n时,那么删除掉p的下一个指针就完成了要求。

  • 设置虚拟节点dummyHead指向head

  • 设定双指针pq,初始都指向虚拟节点dummyHead

  • 移动q,直到pq之间相隔的元素个数为n

  • 同时移动pq,直到q指向的为NULL

  • p的下一个节点指向下下个节点

动画演示

动画演示GIF有点大,请稍微等待一下加载显示^_^

每天一算:Remove Nth Node From End of List

参考代码

每天一算:Remove Nth Node From End of List

每天一算:Remove Nth Node From End of List


本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 每天一算:Remove Nth Node From End of List

我还会在以下平台发布内容

GitHub 哔哩哔哩