剑指offer之面试题15 :链表中倒数第k个结点
题目:输入一个链表,输出该链表中倒数第k个结点。
思路:
两个指针,两个指针距离k个结点,当走在前面的指针已经走到NULL,后面的指针刚好走到倒数第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) { //边界条件1:pListHead指向空即为空链 //边界条件2:k<=0,倒数的大小为正 if(pListHead==NULL||k<=0) { return NULL; } ListNode* pcur1=pListHead; ListNode *pcur2=pListHead ; while(k>0) { k--; //边界条件3:链表不够长,没有倒数第k个结点 if(pcur1!=NULL) { pcur1=pcur1->next; } else { return NULL; } } while(pcur1!=NULL) { pcur1=pcur1->next; pcur2=pcur2->next; } return pcur2; } };