链表中环的入口结点－C++

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

// 面试题23：链表中环的入口结点 // 题目：一个链表中包含环，如何找出环的入口结点？例如，在图3.8的链表中， // 环的入口结点是结点3。 #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 *MeetingNode(ListNode *pHead) { if (pHead == nullptr) return nullptr; ListNode *pSlow = pHead->m_pNext; if (pSlow == nullptr) return nullptr; ListNode *pFast = pSlow->m_pNext; while (pFast != nullptr && pSlow != nullptr) { if (pFast == pSlow) return pFast; pSlow = pSlow->m_pNext; pFast = pFast->m_pNext; if (pFast != nullptr) pFast = pFast->m_pNext; } return nullptr; } ListNode *EntryNodeOfLoop(ListNode *pHead) { ListNode *meetingNode = MeetingNode(pHead); if (meetingNode == nullptr) return nullptr; // 得到环中结点的数目 int nodesInLoop = 1; ListNode *pNode1 = meetingNode; while (pNode1->m_pNext != meetingNode) { pNode1 = pNode1->m_pNext; ++nodesInLoop; } // 先移动pNode1，次数为环中结点的数目 pNode1 = pHead; for (int i = 0; i < nodesInLoop; ++i) pNode1 = pNode1->m_pNext; // 再移动pNode1和pNode2 ListNode *pNode2 = pHead; while (pNode1 != pNode2) { pNode1 = pNode1->m_pNext; pNode2 = pNode2->m_pNext; } return pNode1; } // ==================== Test Code ==================== void Test(char *testName, ListNode *pHead, ListNode *entryNode) { if (testName != nullptr) printf("%s begins: ", testName); if (EntryNodeOfLoop(pHead) == entryNode) printf("Passed.\n"); else printf("FAILED.\n"); } // A list has a node, without a loop void Test1() { ListNode *pNode1 = CreateListNode(1); Test("Test1", pNode1, nullptr); DestroyList(pNode1); } // A list has a node, with a loop void Test2() { ListNode *pNode1 = CreateListNode(1); ConnectListNodes(pNode1, pNode1); Test("Test2", pNode1, pNode1); delete pNode1; pNode1 = nullptr; } // A list has multiple nodes, with a loop void Test3() { 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); ConnectListNodes(pNode5, pNode3); Test("Test3", pNode1, pNode3); delete pNode1; pNode1 = nullptr; delete pNode2; pNode2 = nullptr; delete pNode3; pNode3 = nullptr; delete pNode4; pNode4 = nullptr; delete pNode5; pNode5 = nullptr; } // A list has multiple nodes, with a loop void Test4() { 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); ConnectListNodes(pNode5, pNode1); Test("Test4", pNode1, pNode1); delete pNode1; pNode1 = nullptr; delete pNode2; pNode2 = nullptr; delete pNode3; pNode3 = nullptr; delete pNode4; pNode4 = nullptr; delete pNode5; pNode5 = nullptr; } // A list has multiple nodes, with a loop void Test5() { 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); ConnectListNodes(pNode5, pNode5); Test("Test5", pNode1, pNode5); delete pNode1; pNode1 = nullptr; delete pNode2; pNode2 = nullptr; delete pNode3; pNode3 = nullptr; delete pNode4; pNode4 = nullptr; delete pNode5; pNode5 = nullptr; } // A list has multiple nodes, without a loop void Test6() { 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); Test("Test6", pNode1, nullptr); DestroyList(pNode1); } // Empty list void Test7() { Test("Test7", nullptr, nullptr); } int main(int argc, char *argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); Test7(); return 0; } // ------ Output ------ /* Test1 begins: Passed. Test2 begins: Passed. Test3 begins: Passed. Test4 begins: Passed. Test5 begins: Passed. Test6 begins: Passed. Test7 begins: Passed. */