剑指offer第六天-----获取链表中倒数最后k个结点

剑指offer第六天-----获取链表中倒数最后k个结点

 自己拿到手首先想的是递归，最终提交的时候可以通过量小的例子，在大数据量的链表会发生堆栈越界报错。以下为代码：

import java.util.*;



public class Solution {
    
    int i=1;   //判断当前节点是倒数第几个
    ListNode ls=null;  //返回的头点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if(ls!=null) return ls;
        if(pHead!=null&&pHead.next!=null){
            FindKthToTail(pHead.next,k);
            i++;
            if(i==k)
            {ls=pHead; return ls;}
        }
        return ls;
    }
}

这个空间复杂度太高了，，，

另一种奇怪的方法

设置快慢指针。快指针先走k步，要是走过头了就返回空，否则就设置慢指针为头结点，然后俩指针一起走，直到快指针为空，此时的慢指针所指就是倒数第k节点（因为快慢指针永远相差k个，快的到头了，慢的也就是倒数第k）

代码如下：

import java.util.*;



public class Solution {
    
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode fast=pHead;
        ListNode low=pHead;
        
        int i=1;
        while(i<=k){
            if(fast==null) {return null;}  //一定注意特殊情况
            fast=fast.next;
            i++;
            
        }
        
        while(fast!=null){
            fast=fast.next;
            low=low.next;
        }
        return low;
        
        
        
        
    }
}

爱小宋！！！！！！！！