题目链接
题目描述:
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
解题思路
常规思路,设置一个指针从头结点遍历到尾结点,再回溯到倒数第k个结点,但由于本题是单链表,显然不能回溯。不过我们可以用两次循环,第一次循环遍历整个链表求出其结点总数,而后再从头遍历到第count - k + 1
个结点,同时也是倒数第k个结点,返回当前指针即可。
代码
cpp
1 | /** |
执行用时:8ms~显然,循环两次不够美丽。此时需要我们继续改进代码,那如何实现一次遍历即可得出结果呢?
改进策略
对于链表问题,遇事不决双指针,而且是快慢指针。
定义两个指针。first
指针先从头结点遍历k - 1
步,当要走第k
步时,first
和second
指针同时遍历(second
也从头结点开始遍历),之后两个指针同步遍历以维护两指针之间的距离k - 1
,直到first
指针走到尾结点时,我们发现second
指针恰好在倒数第k
个结点上,返回second
即可。给出一个示意图:
注意:需要考虑边界问题。
- 输入指针为空;
- 输入链表结点总数小于k;
- 输入k为0时无意义。
对于问题1,我们可以在head前设置一个虚拟头结点dimmyNode
。对于问题2,将循环结束条件设为first -> next
。对于问题3,设置一个记录步数的变量step
并赋初值0
,时刻判断与k-1
的关系。
执行用时:4ms
代码
cpp
1 | class Solution { |
如果有错误或者不严谨的地方,请务必给予指正,十分感谢。