转换成正序
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode node = head;
// 算出k - length
while(node != null) {
k--;
node = node.next;
}
// 算出k对于正序的次序(length + 1 - k)
k = -k + 1;
if(k <= 0) {
return null;
}
// 从1开始数
node = head;
while(k-- > 1) {
node = node.next;
}
return node;
}
}
快慢指针
- 快指针先走k步,然后快慢指针同速向前,等快指针到达尾部,慢指针就是倒数第k个
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode fast = head, slow = head;
// 快指针先行k步
while(k > 0 && fast != null) {
fast = fast.next;
k--;
}
// k还没走完就说明过长
if(k > 0) {
return null;
}
// 快慢指针同行
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}