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

题目：链表中倒数第k个结点

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

思路：先来看我的解法，

1.从头结点开始遍历整个链表，每到一个节点，k就减1

2.根据k最后的值开始讨论，

k>0 说明给的链表长度不够，不存在倒数第k个节点，返回null

k==0，说明倒数第k 个恰好为头结点，所以在遍历完链表后，k恰好减为0

k<0

此时再从链表头部往后走，每走一步，k加一，当k==0的时候，恰好就是倒数第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         ListNode tmp=head;
13         while(tmp!=null){
14             tmp=tmp.next;
15             k--;
16         }
17         if(k>0)return null;
18         else if(k==0) return head;
19         else {
20             while(k!=0){
21                 head=head.next;
22                 k++;
23             }
24             return head;
25         }
26     }
27 }

再学习一下别人的算法：

思路：下面这个算法也很简洁，思想就是先定义两个指向头结点的指针，让其中一个指针先走k步，然后咱两一起走，等你到终点时，我刚好到达倒数第K个位置（因为你比我快了k步，而你此时在终点，那我必定在倒数第K个位置）

 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     }