BM7 链表中环的入口结点

标签：结点 slow ListNode nil fast 链表 pHead BM7 return

https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=295&tqId=23449&ru=%2Fpractice%2Fff05d44dfdb04e1d83bdbdab320efbcb&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295

方案一： 快慢指针

GO

package main
func EntryNodeOfLoop(pHead *ListNode) *ListNode{ if pHead == nil || pHead.Next == nil{ return nil } fast := pHead slow := pHead for fast != nil && fast.Next != nil{ fast = fast.Next.Next slow = slow.Next if fast == slow{ //slow从pHead开始走，fast一次一个node的访问 slow = pHead for fast != slow{ slow = slow.Next fast = fast.Next } return fast } } return nil
} 运行时间 6ms   占用内存 1916KB  

方案二： 用哈希存储

package main
func EntryNodeOfLoop(pHead *ListNode) *ListNode{ if pHead == nil || pHead.Next == nil{ return nil } isVisit := make(map[*ListNode]bool) pc := pHead for pc != nil{ if isVisit[pc]{ return pc } isVisit[pc] = true pc = pc.Next } return nil
} 运行时间 8ms   占用内存 2620KB  

C++

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { if(pHead == nullptr || pHead->next == nullptr){ return nullptr; } ListNode* fast = pHead; ListNode* slow = pHead;
while(fast != nullptr && fast->next != nullptr){ fast = fast->next->next; slow = slow->next; if(fast == slow){ slow = pHead; while(slow != fast){ slow = slow->next; fast = fast->next; } return fast; }   } return nullptr;
} }; 运行时间 6ms   占用内存 776KB  

标签：结点,slow,ListNode,nil,fast,链表,pHead,BM7,return
From： https://www.cnblogs.com/starter-songudi/p/17084030.html