剑指offer——面试题22：链表中倒数第k个节点

注意代码的鲁棒性！

函数：

 1 ListNode* TheLastKthNode(ListNode* pHead,int k)
 2 {
 3     if(pHead==nullptr || k<=0)
 4         return nullptr;
 5     ListNode* quickNode=pHead;
 6     ListNode* slowNode=pHead;
 7     int cnt=1;
 8     while(quickNode->m_pNext!=nullptr&&cnt<k)
 9     {
10         quickNode=quickNode->m_pNext;
11         ++cnt;
12     }
13     if(cnt<k)
14         return nullptr;
15     while(quickNode->m_pNext!=nullptr)
16     {
17         quickNode=quickNode->m_pNext;
18         slowNode=slowNode->m_pNext;
19     }
20     return slowNode;
21 }

View Code

测试代码：

 1 #include"List.h"
 2 
 3 void Test(char* testName,ListNode* pHead,int k,int expect)
 4 {
 5     cout<<testName<<":";
 6     ListNode* result=TheLastKthNode(pHead,k);
 7     if(result==nullptr)
 8     {
 9         cout<<"Invalid input."<<endl;
10     }
11     else if(result->m_Value==expect)
12     {
13         cout<<"Passed."<<endl;
14     }
15     else
16         cout<<"Failed."<<endl;
17 }
18 
19 void Test1_7()
20 {
21     ListNode* pNode1=CreateListNode(1);
22 
23     Test("test0",pNode1,1,1);
24     ListNode* pNode2=CreateListNode(2);
25     ListNode* pNode3=CreateListNode(3);
26     ListNode* pNode4=CreateListNode(4);
27     ListNode* pNode5=CreateListNode(5);
28 
29     ConnectListNodes(pNode1,pNode2);
30     ConnectListNodes(pNode2,pNode3);
31     ConnectListNodes(pNode3,pNode4);
32     ConnectListNodes(pNode4,pNode5);
33 
34     Test("test1",pNode1,0,-1);
35     Test("test2",pNode1,1,5);
36     Test("test3",pNode1,2,4);
37     Test("test4",pNode1,3,3);
38     Test("test5",pNode1,4,2);
39     Test("test6",pNode1,5,1);
40 
41     Test("test7",nullptr,5,-1);
42 
43 }
44 
45 int main()
46 {
47     Test1_7();
48     return 0;
49 }

View Code