【面试题】剑指offer 15

2019-11-06 06:29:43

字体：大中小

来源：转载

供稿：网友

题目：输入一个链表，输出该链表的倒数第k个节点。

#include<iostream>#include<cstdlib>using namespace std;struct ListNode{ ListNode* pNext; int _value;};class List{public: List() :pHead(NULL) {} ~List() { delete pHead; pHead=NULL; } void AddNum(const int value) { ListNode* newnode=new ListNode(); if (pHead==NULL) { newnode->_value=value; newnode->pNext=NULL; pHead=newnode; return; } ListNode* node=pHead; while(node->pNext!=NULL) { node=node->pNext; } newnode->_value=value; newnode->pNext=NULL; node->pNext=newnode; } void PRint() { ListNode* cur=pHead; while (cur) { cout<<cur->_value<<" "; cur=cur->pNext; } cout<<endl; } ListNode* FindKToTail(unsigned int k) { if (pHead==NULL) return NULL; if(k<=0) return NULL; ListNode* first=pHead; ListNode* second=NULL; for(unsigned int i=0;i<k-1;i++) { if(first->pNext) first=first->pNext; else return NULL; } second=pHead; while (first->pNext) { first=first->pNext; second=second->pNext; } return second; }private: ListNode* pHead;};void test(){ List l; l.AddNum(1); l.AddNum(2); l.AddNum(3); l.AddNum(4); l.AddNum(5); l.AddNum(6); l.AddNum(7); l.AddNum(8); l.AddNum(9); l.Print(); ListNode* node=l.FindKToTail(4); cout<<node->_value<<endl; l.Print();}#include "List.h"int main(){ test(); system("pause"); return 0;}