25、输入一个链表，输出该链表中倒数第k个结点。

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

提供两种思路。

思路1：正常思维

一共有count个，倒数第k个就是正数第count-k+1,下标是count-k

 1 /*
 2 public class ListNode {
 3     int val;
 4     ListNode next = null;
 5 
 6     ListNode(int val) {
 7         this.val = val;
 8     }
 9 }*/
10 public class Solution {
11     public ListNode FindKthToTail(ListNode head,int k) {
12         if(head == null)
13             return null;
14         int count = 0;
15         ListNode temp = head;
16         for (int i = 0; temp != null; temp = temp.next) {
17             count++;
18         }
19         if(k>count)
20             return null;
21         System.out.println(count);
22         for(int i = 0;i<count-k;i++){
23             head = head.next;
24         }
25         return head;
26     }
27 }

思路2：

相当于制造了一个K长度的尺子，把尺子从头往后移动，当尺子的右端与链表的末尾对齐的时候，尺子左端所在的结点就是倒数第k个结点

 1 public class Solution {
 2     public ListNode FindKthToTail(ListNode head,int k) {
 3         ListNode pre=null,p=null;
 4         //两个指针都指向头结点
 5         p=head;
 6         pre=head;
 7         //记录k值
 8         int a=k;
 9         //记录节点的个数
10         int count=0;
11         //p指针先跑，并且记录节点数，当p指针跑了k-1个节点后，pre指针开始跑，
12         //当p指针跑到最后时，pre所指指针就是倒数第k个节点
13         while(p!=null){
14             p=p.next;
15             count++;
16             if(k<1){
17                 pre=pre.next;
18             }
19             k--;
20         }
21         //如果节点个数小于所求的倒数第k个节点，则返回空
22         if(count<a) return null;
23         return pre;
24             
25     }
26 }

精简后：

 1 public ListNode FindKthToTail(ListNode head,int k) { //5,{1,2,3,4,5}
 2         ListNode p, q;
 3         p = q = head;
 4         int i = 0;
 5         for (; p != null; i++) {
 6             if (i >= k) 
 7                 q = q.next;
 8             p = p.next;
 9         }
10         return i < k ? null : q;
11     }