题解 | #链表中倒数最后k个结点#
链表中倒数最后k个结点
http://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9
1、快慢指针：时间复杂度是O(n),空间复杂度O(1)
思路：快指针比慢指针多走K步，当快指针走完时，慢指针正好是倒数第K个
public ListNode FindKthToTail (ListNode pHead, int k) {
if(pHead==null){
return null;
}
ListNode slow = pHead;
ListNode fast = pHead;
while(fast!=null&&k>0){
fast=fast.next;
k--;
}
if(k>0){
return null;
}
while(fast!=null){
slow=slow.next;
fast=fast.next;
}
return slow;
}
2、统计链表长度：时间复杂度是O(n),空间复杂度O(1)
思路：通过统计链表的长度，计算倒数第K个是正数第几个，遍历链表到当前位置停下来。
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
int s = 0;
//统计链表长度
ListNode node = pHead;
while(node!=null){
node=node.next;
s++;
}
if(s<k){
return null;
}
//计算是第几个停下来
int target = s-k;
s=0;
while(s<target){
pHead = pHead.next;
s++;
}
return pHead;
}
