剑指offer-链表中倒数第k个结点

• 用栈的解法：链表中倒数的节点，自然想到遍历+栈。弹出栈中第k个元素即可；

  import java.util.Stack;
  public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null || k==0){
            return null;
        }
  
        int len=0,i;
        Stack<ListNode> s = new Stack<>();
        int cur;
  
        while(head!=null){
            s.push(head);
            head=head.next;
            len++;
        }
        //如果k大于链表长度，返回null
        if(len<k){
            return null;
        }else{
            //k=1不会进入这个循环而是直接return s.pop();
            //边界条件是k>=2！此处循环次数是k-1
            while(!s.isEmpty() && k>=2){
                s.pop();
                k--;
            }
        }
        return s.pop();
    }
  }

  在代码实现中出栈次数的边界条件是while(!s.isEmpty()&&k>=2)，k>=2原因是Java索引从0开始，所以至少要使得k>=1，而在return时pop了一次，所以循环的次数要-1，即k>=2。

• 快慢指针
  快指针先走k步，然后快慢指针一起走。当快指针来到链表最后指向null时，慢指针指向的是倒数第k个节点。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null || k==0){
            return null;
        }

        ListNode fast=head;
        ListNode slow=head;
        while(k>=1){
            //如果k大于链表长度，返回null
            if(fast==null){
                return null;
            }
            fast=fast.next;
            k--;
        } 
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
    return slow;

}

快慢指针题目合集：https://mp.weixin.qq.com/s/5t_dlnrceoSoIM1snxmBdw