package demo;

public class Solution {

    public static class ListNode{

        int val;

        ListNode next = null;

        ListNode(int val){

            this.val = val;

        }

    }

    public static ListNode findKthtoTail(ListNode head, int k){

        if(head == null || k<1){

            return null;

        }

        ListNode pre = head;

        for(int i=0; i<k-1;i++){//先将pre指针移到第k-1位

            if(pre.next != null)

                pre = pre.next;

            else

                return null;

        }

        ListNode cur = head;

        while(pre.next != null){//遍历

            pre = pre.next;

            cur = cur.next;

        }

        return cur;

    }

    public static void main(String[] args) {

        ListNode head = new ListNode(0);

        ListNode node1 = new ListNode(1); head.next = node1;

        ListNode node2 = new ListNode(2); node1.next = node2;

        ListNode node3 = new ListNode(3); node2.next = node3;

        ListNode node4 = new ListNode(4); node3.next = node4;

        ListNode node5 = new ListNode(5); node4.next = node5;

        ListNode node6 = new ListNode(6); node5.next = node6;

        ListNode node7 = new ListNode(7); node6.next = node7;

        ListNode node8 = new ListNode(8); node7.next = node8;

        ListNode node9 = new ListNode(9); node8.next = node9;

        ListNode node10 = new ListNode(10); node9.next = node10;

        ListNode cur = head;

        while(cur.next != null){

            cur = cur.next;

            System.out.print(cur.val + " ");

        }

        int k = 4;

        ListNode resNode = findKthtoTail(head, k);

        System.out.println("\n链表倒数第"+k+"个元素为：" + resNode.val);

    }

}