题目地址:https://leetcode-cn.com/submissions/detail/186081706/
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。示例:给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
这道题的思路是,先找到最后一个节点,然后在找到倒数第k节点。
当然这里可以用到我们的快慢指针,我的爆破法也是这样
一、爆破法
快慢指针,比如我们k=2,获取的就是倒数第二个数字,那么快针就比满针多1,所以我们想到,让快针先跑k-1步,然后开始循环让快慢针一起跑。(我先让你走k-1步hhhhh)
最终如果快针的next= null 说明快针是最后一个节点,那么只需要返回慢针即可
执行结果如下:
208 / 208 个通过测试用例
状态:通过
执行用时: 0 ms
内存消耗: 36 MB
public static ListNode getKthFromEndMe(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
// 快针先跑
for(int i = 1;i <k;i++){
fast = fast.next;
}
while(null != fast.next){
fast = fast.next;
slow = slow.next;
}
return slow;
}
这道题很好,让我复习了昨天学习的快慢针,总体来说如果不知道快慢针的话可能会比较麻烦。
因为结果几乎是双百,评论区也没有更好的办法,所以这题直接就这样结束吧,next