《剑指offer》 第22题 链表中倒数第k个数

题目描述
输入一个链表，输出该链表中倒数第k个结点。

思路1：先遍历一遍，获得长度，然后第二遍得到倒数第k个节点。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {

    int length = 0;
    ListNode node = head;
    while (node != null) {
        ++length;
        node = node.next;
    }
    if (k > length) {
        return null;
    }
    node = head;
    for (int i = 0; i < length - k; ++i) {
        node = node.next;
    }
    return node;
    }
}

思路2：利用栈的性质，在弹栈的时候，可以获得倒数第k个节点。(也可以用数组等其他数据结构存，然后再取)

import java.util.Stack;
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {

    Stack<ListNode> stack=new Stack<ListNode>();
    while (head!=null){
        stack.push(head);
        head=head.next;
    }
    int len=stack.size();
    if(len==0||len<k||k==0){
        return null;
    }
    ListNode result=stack.pop();
    while (result!=null){
        k--;
        if(k==0){
            return result;
        }
        result=stack.pop();

    }
    return  null;
        }
}

思路3：快慢指针，快指针速度和慢指针一样，但是位置上领先k，所以快指针到达尾节点时，慢指针到达倒数第k个节点。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode fast=head;
        ListNode slow=head;

        for (int i = 0; i <k ; i++) {
            if(fast==null){
                return null;
            }
            fast=fast.next;
        }
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
        }
}

补充：书上第23题求环的入口节点也是快慢指针，此时快指针速度是慢指针的两倍，相遇则是环的入口