题目
输入一个链表，输出该链表中倒数第k个结点。
思路
两个指针，p1，p2。p1先走(k-1)步，然后p1，p2同时走，当p1走到最后一个结点的时候p2指向的就是倒数第k个结点。
示例
输入表的结点值为：0,1,2,3,4,5,6 求倒数第2个 输出： 5 5
代码
#include <iostream>
using namespace std;
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* p1(pListHead),*p2(pListHead),*dj(pListHead);
//判断指针是否为空，以及k是否越界
int size(0);
// 链表长度
while(dj != NULL)
{
dj = dj -> next;
size ++;
}
if(k > size) {
return nullptr;
}
for (int i = 1; i < k; ++i) {
p1 = p1 -> next;
}
while (p1->next != NULL){
p1 = p1 -> next;
p2 = p2 -> next;
//cout<< p1->val;
}
return p2;
}
// 上述代码优化
ListNode* FindKthToTail1(ListNode* listNode, unsigned int k){
ListNode* p(listNode);
for (int i = 0; i < k; ++i) {
if(!p)
return nullptr ;
else
p = p ->next;
}
while (p){
p = p ->next;
listNode = listNode -> next;
}
return listNode;
}
};
int main(){
Solution re;
int k(2);
struct ListNode* head,*list,*pinput;
struct ListNode node(0);
pinput = head = list = &node;
for (int i = 1; i < 7; ++i) {
struct ListNode *p = new ListNode(i);
head -> next = p;
head = head -> next;
}
while (pinput!=NULL){
cout << pinput->val;
pinput = pinput -> next;
}
cout << endl;
cout << re.FindKthToTail(list,k)->val << endl;
cout << re.FindKthToTail1(list,k)->val;
}
