返回倒数第k个节点

返回倒数第k个节点

思路1：首先计算链表长度，让链表长度-倒数第k得到的数字（ret），定义一个变量cur指向头节点，让cur走上ret次，即可找到倒数第k个节点

class Solution {public int size(ListNode head){if(head==null){return 0;}ListNode cur=head;int count =0;while (cur!=null){count++;cur=cur.next;}return count;}public int kthToLast(ListNode head, int k) {int count=size(head);ListNode cur=head;int ret=count-k;while(ret!=0){cur=cur.next;ret--;}return cur.val;}
}

思路1需要遍历链表两次，有没有只遍历一次，就能找到倒数第k个节点呢？

思路2：定义那个变量指向头节点分别为fast和slowfast比slow多走k步，当fast指向的对象为空时，slow就指向倒数第k个节点啦
1.初始化双指针 fast , slow都指向头节点 head ；
2.先令 fast 走 k 步，此时fast , slow 的距离为 k ；
3.令 fast , slow一起走，直到 cur 走过尾节点时跳出，此时 pre 指向「倒数第 k 个节点」，返回之即可

class Solution {public int kthToLast(ListNode head, int k) {ListNode fast=head;ListNode slow=head;while(fast!=null){while (k!=0){//让fast多走k步fast=fast.next;k--;}fast=fast.next;slow=slow.next;}return slow.val;}
}