JZ-C-15

剑指offer第十五题：链表中倒数第K个结点
  1 //============================================================================
  2 // Name        : JZ-C-15.cpp
  3 // Author      : Laughing_Lz
  4 // Version     :
  5 // Copyright   : All Right Reserved
  6 // Description : 链表中倒数第K个结点
  7 //============================================================================
  8 
  9 #include <iostream>
 10 #include "List.h"
 11 #include <stdio.h>
 12 using namespace std;
 13 
 14 ListNode* FindKthToTail(ListNode* node, unsigned int k) {
 15     if (k == 0 || node == NULL) {
 16         return NULL;
 17     }
 18     ListNode* head = node;
 19     ListNode* follow = node;
 20     for (unsigned int i = 0; i < k - 1; i++) {
 21         if (head->m_pNext == NULL) {
 22             return NULL;
 23         } else {
 24             head = head->m_pNext;
 25         }
 26     }
 27     while (head->m_pNext != NULL) {
 28         head = head->m_pNext;
 29         follow = follow->m_pNext;
 30     }
 31     return follow;
 32 }
 33 
 34 // ====================测试代码====================
 35 // 测试要找的结点在链表中间
 36 void Test1() {
 37     printf("=====Test1 starts:=====
");
 38     ListNode* pNode1 = CreateListNode(1);
 39     ListNode* pNode2 = CreateListNode(2);
 40     ListNode* pNode3 = CreateListNode(3);
 41     ListNode* pNode4 = CreateListNode(4);
 42     ListNode* pNode5 = CreateListNode(5);
 43 
 44     ConnectListNodes(pNode1, pNode2);
 45     ConnectListNodes(pNode2, pNode3);
 46     ConnectListNodes(pNode3, pNode4);
 47     ConnectListNodes(pNode4, pNode5);
 48 
 49     printf("expected result: 4.
");
 50     ListNode* pNode = FindKthToTail(pNode1, 2);
 51     PrintListNode(pNode);
 52 
 53     DestroyList(pNode1);
 54 }
 55 
 56 // 测试要找的结点是链表的尾结点
 57 void Test2() {
 58     printf("=====Test2 starts:=====
");
 59     ListNode* pNode1 = CreateListNode(1);
 60     ListNode* pNode2 = CreateListNode(2);
 61     ListNode* pNode3 = CreateListNode(3);
 62     ListNode* pNode4 = CreateListNode(4);
 63     ListNode* pNode5 = CreateListNode(5);
 64 
 65     ConnectListNodes(pNode1, pNode2);
 66     ConnectListNodes(pNode2, pNode3);
 67     ConnectListNodes(pNode3, pNode4);
 68     ConnectListNodes(pNode4, pNode5);
 69 
 70     printf("expected result: 5.
");
 71     ListNode* pNode = FindKthToTail(pNode1, 1);
 72     PrintListNode(pNode);
 73 
 74     DestroyList(pNode1);
 75 }
 76 
 77 // 测试要找的结点是链表的头结点
 78 void Test3() {
 79     printf("=====Test3 starts:=====
");
 80     ListNode* pNode1 = CreateListNode(1);
 81     ListNode* pNode2 = CreateListNode(2);
 82     ListNode* pNode3 = CreateListNode(3);
 83     ListNode* pNode4 = CreateListNode(4);
 84     ListNode* pNode5 = CreateListNode(5);
 85 
 86     ConnectListNodes(pNode1, pNode2);
 87     ConnectListNodes(pNode2, pNode3);
 88     ConnectListNodes(pNode3, pNode4);
 89     ConnectListNodes(pNode4, pNode5);
 90 
 91     printf("expected result: 1.
");
 92     ListNode* pNode = FindKthToTail(pNode1, 5);
 93     PrintListNode(pNode);
 94 
 95     DestroyList(pNode1);
 96 }
 97 
 98 // 测试空链表
 99 void Test4() {
100     printf("=====Test4 starts:=====
");
101     printf("expected result: NULL.
");
102     ListNode* pNode = FindKthToTail(NULL, 100);
103     PrintListNode(pNode);
104 }
105 
106 // 测试输入的第二个参数大于链表的结点总数
107 void Test5() {
108     printf("=====Test5 starts:=====
");
109     ListNode* pNode1 = CreateListNode(1);
110     ListNode* pNode2 = CreateListNode(2);
111     ListNode* pNode3 = CreateListNode(3);
112     ListNode* pNode4 = CreateListNode(4);
113     ListNode* pNode5 = CreateListNode(5);
114 
115     ConnectListNodes(pNode1, pNode2);
116     ConnectListNodes(pNode2, pNode3);
117     ConnectListNodes(pNode3, pNode4);
118     ConnectListNodes(pNode4, pNode5);
119 
120     printf("expected result: NULL.
");
121     ListNode* pNode = FindKthToTail(pNode1, 6);
122     PrintListNode(pNode);
123 
124     DestroyList(pNode1);
125 }
126 
127 // 测试输入的第二个参数为0
128 void Test6() {
129     printf("=====Test6 starts:=====
");
130     ListNode* pNode1 = CreateListNode(1);
131     ListNode* pNode2 = CreateListNode(2);
132     ListNode* pNode3 = CreateListNode(3);
133     ListNode* pNode4 = CreateListNode(4);
134     ListNode* pNode5 = CreateListNode(5);
135 
136     ConnectListNodes(pNode1, pNode2);
137     ConnectListNodes(pNode2, pNode3);
138     ConnectListNodes(pNode3, pNode4);
139     ConnectListNodes(pNode4, pNode5);
140 
141     printf("expected result: NULL.
");
142     ListNode* pNode = FindKthToTail(pNode1, 0);
143     PrintListNode(pNode);
144 
145     DestroyList(pNode1);
146 }
147 
148 int main(int argc, char** argv) {
149     Test1();
150     Test2();
151     Test3();
152     Test4();
153     Test5();
154     Test6();
155 
156     return 0;
157 }