题目：输入一个链表，输出该链表中倒数第K个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

看到这道题目，最直观的想法，就是先算出链表的长度n，然后倒数第k个结点就是顺序的第(n-k+1)个数，不过这样需要2次遍历链表，如果要求只能遍历链表一次，那么上述算法就不符合要求了。

那我们就使用第二种算法，设定两个指针p1和p2，两个指针刚开始都指向链表的第一个结点，然后让p1指针先走(k-1)步，然后再让两个指针一起往后走，当p1指针指向链表最后一个结点的时候，p2指针刚好指向链表中的倒数第k个结点。

在写代码的时候需要考虑鲁棒性，***采用防御性编程，就是考虑在哪些地方会出错，然后提前加上错误判断，这样避免因此错误输入而导致程序崩溃。

下面首先给出代码实例，然后再讲解程序鲁棒性：

View Code

上述程序中，求倒数第k个结点的第一个方法：ListNode* KthNodeFromEnd(ListNode* pHead,int k)。

这个方法看似满足了我们的题目要求，但是当我们仔细分析，发现有3中方法让程序崩溃

1. 输入的pListHead为空指针，由于代码会尝试访问空指针指向的内存，程序崩溃
2. 输入的以pListHead为头结点的链表的结点少于k。这样在while(k-1>0)的循环中，又会出现尝试访问空指针指向的内存。
3. 输入的参数k小于等于0。根据题意k的最小值应为1。

 考虑上述因素，我们给出了第二个方法：ListNode* KthNodeFromEnd2(ListNode* pHead,int k)。

相关题目

1.求链表的中间结点。如果链表中结点总数为奇数，返回中间结点；如果结点总数是偶数，返回中间两个结点的任意一个。为了解决这个问题，我们也可以定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。

代码实例如下：

View Code

2.判断一个单向链表是否形成了环状结构。和前面的问题一样，定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另外一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环状结构；如果走得快的指针走到了链表的末尾（m_pNext指向NULL）都没有追上走得慢的指针，那么链表就不是环状结构。

代码实例如下：

View Code

 本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2012/04/27/2473355.html，如需转载请自行联系原作者