题解 | #链表中环的入口结点#
链表中环的入口结点
https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* MeetNode(ListNode* pHead) { if(pHead==nullptr) return nullptr; ListNode* pSlow=pHead; ListNode* pFast=pHead; while(pFast!=nullptr&&pFast->next!=nullptr) { pFast=pFast->next->next; pSlow=pSlow->next; if(pSlow==pFast) return pFast; } return nullptr; } ListNode* EntryNodeOfLoop(ListNode* pHead) { ListNode* meetNode=MeetNode(pHead); if(meetNode==nullptr) return nullptr; ListNode* pNode1=pHead; ListNode* pNode2=meetNode; while (pNode1!=pNode2) { pNode1=pNode1->next; pNode2=pNode2->next; } return pNode1; } };
1.注意快指针比慢指针快一倍
2.注意相遇点为nullptr需要处理下
在相遇点和头节点处,一定是可以进行相遇的
#剑指OFFER#