每天一算: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


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

GitHub 知乎