输入一个链表，输出该链表中倒数第k个结点。
struct ListNode { int m_nValue; ListNode *m_pNext; }; ListNode* CreateListNode(int value) { ListNode* pNode = new ListNode(); pNode->m_nValue = value; pNode->m_pNext = NULL; return pNode; } void ConnectListNodes(ListNode* pCurrent, ListNode* pNext) { if(pCurrent == NULL) { printf("Error to connect two nodes.\n"); } pCurrent->m_pNext = pNext; } void PrintListNode(ListNode* pNode) { if(pNode == NULL) { printf("The node is NULL\n"); } else { printf("The key in node is %d.\n", pNode->m_nValue); } } ListNode *FindKth(ListNode *pListHead,unsigned int k) { if(pListHead == NULL || k == 0) return NULL; ListNode *pAhead = pListHead; ListNode *pBehind = NULL; for(unsigned int i=0;i<k-1;++i) { if(pAhead->m_pNext != NULL) pAhead = pAhead->m_pNext; else { return NULL; } } pBehind = pListHead; while(pAhead->m_pNext != NULL) { pAhead = pAhead->m_pNext; pBehind = pBehind->m_pNext; } return pBehind; } void DestroyList(ListNode* pHead) { ListNode* pNode = pHead; while(pNode != NULL) { pHead = pHead->m_pNext; delete pNode; pNode = pHead; } } void Test1() { printf("=====Test1 starts:=====\n"); ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); printf("expected result: 4.\n"); ListNode* pNode = FindKth(pNode1, 2); PrintListNode(pNode); DestroyList(pNode1); } void Test2() { printf("=====Test2 starts:=====\n"); ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); printf("expected result: 5.\n"); ListNode* pNode = FindKth(pNode1, 1); PrintListNode(pNode); DestroyList(pNode1); } void Test3() { printf("=====Test3 starts:=====\n"); ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); printf("expected result: 1.\n"); ListNode* pNode = FindKth(pNode1, 5); PrintListNode(pNode); DestroyList(pNode1); } void Test4() { printf("=====Test4 starts:=====\n"); printf("expected result: NULL.\n"); ListNode* pNode = FindKth(NULL, 100); PrintListNode(pNode); } void Test5() { printf("=====Test5 starts:=====\n"); ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); printf("expected result: NULL.\n"); ListNode* pNode = FindKth(pNode1, 6); PrintListNode(pNode); DestroyList(pNode1); } void Test6() { printf("=====Test6 starts:=====\n"); ListNode* pNode1 = CreateListNode(1); ListNode* pNode2 = CreateListNode(2); ListNode* pNode3 = CreateListNode(3); ListNode* pNode4 = CreateListNode(4); ListNode* pNode5 = CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); printf("expected result: NULL.\n"); ListNode* pNode = FindKth(pNode1, 0); PrintListNode(pNode); DestroyList(pNode1); } int main() { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); return 0; }
