本文主要是介绍剑指Offer15链表中倒数第k个结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
输入一个链表，输出该链表中倒数第k个结点，为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第一个结点，例如：一个链表有6个结点，从头结点开始他们的值依次是1,2,3,4,5,6.这个链表的倒数第三个结点是值为4的结点。
分析：
这是一个很经典的老的题，如果第一次看到这个题的话，可能想的是遍历一边链表得到长度为n，然后再从头来一边，找到第n-k个链表，就是倒数第k个结点。那么时间复杂度就是O(n)，但是如果告诉你还有一种方法使得它只遍历一边就能得到结果，你会怎么想？
可能就会做一个k大小的队列，当队列的头指向了最后一个结点的时候，那队列的尾指向的就是此链表的倒数第k个结点。但是如果题目要求你只有常数的空间复杂度怎么办。其实能想到队列，这个题就基本相当于想到了最佳答案，因为在队列里，只用到了头和尾，中间的存储空间是没有用的，那么我们就把中间的都去掉，只留下头和尾，就相当于用两个指针，第一个指针先向前移动k个结点，然后第二个指针跟着第一个指针依次向后移动，直到第一个指针指向链表的尾结点，那么第二个指针指向的就是倒数第k个结点。
能想到这一点，这个题就算做完了？
没有吧！
如果k比链表的总长度还大怎么办？
所以代码的鲁棒性就要很好的体现了！
下面看代码：
int FindLastKNode(ListNode * headList,int k)
{if(headList == NULL || k <= 0)return -1;ListNode *p = headList;ListNode *pNext = headList;for(int i=0;i<k;i++){if(pNext == NULL)return -1;pNext = pNext->m_pNext;}while(pNext != NULL){pNext = pNext->m_pNext;p = p->m_pNext;}return p->m_nValue;
}剑指Offer这本书上还对此题目进行了扩展，有几个扩展的题目还是比较不错的
1.求链表的中间结点。如果链表的结点总数为奇数，返回中间结点，如果结点总数是偶数，返回中间两个结点的任意一个。
答：我们也可以定义两个指针，都同时指向头结点，一个指针一次走一步，另一个指针一次走两步。当走的快的那个指针指向了尾结点，那么走的慢的指针就指向的中间结点。
2.判断一个单项链表是不是形成了环形结构。
这个问题和前面的问题一样，一个走两步，一个走两步，如果走的快的指针追上了走的慢的，那么就是有环的。如果走的快的指向了尾结点，那么说明这个链表没有环。
总结：
当我们尝试用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表，可以让其中一个指针速度快点，或者让它先走几步。
这篇关于剑指Offer15链表中倒数第k个结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
