链表中倒数第k个结点－C++

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程https://www.captainai.net/troubleshooter

// 面试题22：链表中倒数第k个结点 // 题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯， // 本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点， // 从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是 // 值为4的结点。 #include <cstdio> #include <stdio.h> #include <stdlib.h> struct ListNode { int m_nValue; ListNode *m_pNext; }; ListNode *CreateListNode(int value) { ListNode *pNode = new ListNode(); pNode->m_nValue = value; pNode->m_pNext = nullptr; return pNode; } void ConnectListNodes(ListNode *pCurrent, ListNode *pNext) { if (pCurrent == nullptr) { printf("Error to connect two nodes.\n"); exit(1); } pCurrent->m_pNext = pNext; } void PrintListNode(ListNode *pNode) { if (pNode == nullptr) { printf("The node is nullptr\n"); } else { printf("The key in node is %d.\n", pNode->m_nValue); } } void PrintList(ListNode *pHead) { printf("PrintList starts.\n"); ListNode *pNode = pHead; while (pNode != nullptr) { printf("%d\t", pNode->m_nValue); pNode = pNode->m_pNext; } printf("\nPrintList ends.\n"); } void DestroyList(ListNode *pHead) { ListNode *pNode = pHead; while (pNode != nullptr) { pHead = pHead->m_pNext; delete pNode; pNode = pHead; } } void AddToTail(ListNode **pHead, int value) { ListNode *pNew = new ListNode(); pNew->m_nValue = value; pNew->m_pNext = nullptr; if (*pHead == nullptr) { *pHead = pNew; } else { ListNode *pNode = *pHead; while (pNode->m_pNext != nullptr) pNode = pNode->m_pNext; pNode->m_pNext = pNew; } } void RemoveNode(ListNode **pHead, int value) { if (pHead == nullptr || *pHead == nullptr) return; ListNode *pToBeDeleted = nullptr; if ((*pHead)->m_nValue == value) { pToBeDeleted = *pHead; *pHead = (*pHead)->m_pNext; } else { ListNode *pNode = *pHead; while (pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue != value) pNode = pNode->m_pNext; if (pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue == value) { pToBeDeleted = pNode->m_pNext; pNode->m_pNext = pNode->m_pNext->m_pNext; } } if (pToBeDeleted != nullptr) { delete pToBeDeleted; pToBeDeleted = nullptr; } } ListNode *FindKthToTail(ListNode *pListHead, unsigned int k) { if (pListHead == nullptr || k == 0) return nullptr; ListNode *pAhead = pListHead; ListNode *pBehind = nullptr; for (unsigned int i = 0; i < k - 1; ++i) { if (pAhead->m_pNext != nullptr) pAhead = pAhead->m_pNext; else { return nullptr; } } pBehind = pListHead; while (pAhead->m_pNext != nullptr) { pAhead = pAhead->m_pNext; pBehind = pBehind->m_pNext; } return pBehind; } // ====================测试代码==================== // 测试要找的结点在链表中间 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 = FindKthToTail(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 = FindKthToTail(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 = FindKthToTail(pNode1, 5); PrintListNode(pNode); DestroyList(pNode1); } // 测试空链表 void Test4() { printf("=====Test4 starts:=====\n"); printf("expected result: nullptr.\n"); ListNode *pNode = FindKthToTail(nullptr, 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: nullptr.\n"); ListNode *pNode = FindKthToTail(pNode1, 6); PrintListNode(pNode); DestroyList(pNode1); } // 测试输入的第二个参数为0 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: nullptr.\n"); ListNode *pNode = FindKthToTail(pNode1, 0); PrintListNode(pNode); DestroyList(pNode1); } int main(int argc, char *argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); return 0; } // ------ Output ------ /* =====Test1 starts:===== expected result: 4. The key in node is 4. =====Test2 starts:===== expected result: 5. The key in node is 5. =====Test3 starts:===== expected result: 1. The key in node is 1. =====Test4 starts:===== expected result: nullptr. The node is nullptr =====Test5 starts:===== expected result: nullptr. The node is nullptr =====Test6 starts:===== expected result: nullptr. The node is nullptr */