剑指Offer第十四题：链表中倒数第k个结点

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

解答：
1.放到栈中进行中转
public class Q_14 {

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;
}
public static void main(String[] args) {
    ListNode node1=new ListNode(1);
    ListNode node2=new ListNode(2);
    ListNode node3=new ListNode(3);
    ListNode node4=new ListNode(4);
    ListNode node5=new ListNode(5);

    node1.next=node2;
    node2.next=node3;
    node3.next=node4;
    node4.next=node5;
    System.out.println(new Q_14().FindKthToTail1(node1, 5).val);
}

}

2.快慢指针
思想：快指针先前进k位，然后和慢指针同步前进，则慢指针就是倒数k位
public class Q_14 {

public ListNode FindKthToTail1(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;
}

public static void main(String[] args) {
    ListNode node1=new ListNode(1);
    ListNode node2=new ListNode(2);
    ListNode node3=new ListNode(3);
    ListNode node4=new ListNode(4);
    ListNode node5=new ListNode(5);

    node1.next=node2;
    node2.next=node3;
    node3.next=node4;
    node4.next=node5;
    System.out.println(new Q_14().FindKthToTail1(node1, 5).val);
}

}