Offer22（链表中倒数第k个节点）

题目：

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

思路：

　　此题很明显可以想到倒数第k个节点即是正数第len-k+1个节点，但为了求链表的长度，我们解此题需要遍历链表两次。为了只遍历一次，我们可以使用双指针。
让前面的指针先走k-1步，这样当前面的指针到达尾节点时，后面的节点即为倒数第k个节点。

代码：

  public ListNode FindKthToTail(ListNode head,int k) {
  	if (head == null || k <= 0) {
	return null;
}
  	ListNode preHead = head;
  	ListNode curHead = head;
  	for(int i = 0;i < k - 1;i++) {
  		curHead = curHead.next;
  	}
  	if (curHead == null) {
	return null;
}
  	while(curHead.next != null) {
  		preHead = preHead.next;
  		curHead = curHead.next;
  	}
  	return preHead;
  }

复杂度分析：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

相关题目：

　　求链表的中间节点。

总结：

　　当想优化链表遍历次数时，可以考虑使用双指针。