题目：链表中倒数第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     }