剑指offer

题目描述

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

两种比较简答的解法：1：先对链表遍历一遍统计节点个数count，然后从链表头走count-k+1步刚好达到倒数第k个节点。

需要注意的是：第一次遍历前需要保存一下输入的链表，等下第二次寻找需要用，不然报错啊。如下代码：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { //保存一下链表的表头，等下第二次遍历需要，不然会出错 ListNode* pListNode = pListHead; if(pListHead==nullptr&&k==0) return nullptr; unsigned int count = 0; while(pListHead!=nullptr){ ++count; pListHead = pListHead->next; } if(count<k) return nullptr; //ListNode* pNode; for(unsigned int i=1;i<count-k+1;++i){ pListNode = pListNode->next; } ListNode* pNode = pListNode; return pNode; } };

方法2：使用同向双指针，前指针先走k步，然后，后指针和前指针一起走，当前头指针到nullptr时，后面的指针就是倒数第k个节点。代码见剑指offer书。