// 面试题23：链表中环的入口结点 // 题目：一个链表中包含环，如何找出环的入口结点？例如，在图3.8的链表中， // 环的入口结点是结点3。 #include <cstdio> #include "list.h" 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) { //1.首先遍历链表查找是否存在环 ListNode* meetingNode = MeetingNode(pHead); if (meetingNode == nullptr) return nullptr; //2.然后算出环的长度n int length = 1; ListNode* pNode = meetingNode; while (pNode->m_pNext != meetingNode) { pNode = pNode->m_pNext; ++length; } //3.接着指针1先走n步 ListNode* pNodeFast = pHead; for (int i = 0; i < length; ++i) pNodeFast = pNodeFast->m_pNext; //4.最后指针12同时往前遍历, 相等时即入口 pNode = pHead; while (pNode != pNodeFast) { pNode = pNode->m_pNext; pNodeFast = pNodeFast->m_pNext; } return pNode; }
// ==================== Test Code ==================== void Test(const char* testName, ListNode* pHead, ListNode* entryNode) { if (testName != nullptr) printf("%s begins: ", testName); if (EntryNodeOfLoop(pHead) == entryNode) printf("Passed. "); else printf("FAILED. "); } // 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; }
分析：双指针解决。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { //1.寻找环 ListNode* meetingNode = MeetingNode(pHead); if (meetingNode == nullptr) return nullptr; //2.确定环长n int length = 1; ListNode* pNode = meetingNode; while (pNode->next != meetingNode) { pNode = pNode->next; ++length; } //3.指针1先走n步 pNode = pHead; for (int i = 0; i < length; ++i) pNode = pNode->next; //4.指针12同时遍历，相遇时即为起点 ListNode* pNode2 = pHead; while (pNode != pNode2) { pNode = pNode->next; pNode2 = pNode2->next; } return pNode; } ListNode* MeetingNode(ListNode* pHead) { if (pHead == nullptr) return nullptr; ListNode* pSlow = pHead->next; if (pSlow == nullptr) return nullptr; ListNode* pFast = pSlow->next; while (pFast != nullptr && pSlow != nullptr) { if (pFast == pSlow) return pFast; pSlow = pSlow->next; pFast = pFast->next; if (pFast != nullptr) pFast = pFast->next; } return nullptr; } };