55链表中环的入口结点

题目描述

一个链表中包含环，请找出该链表的环的入口结点。

利用快慢指针
如果链表的环中有n个节点。快指针先走n步，然后同时走。当慢指针走的入口节点的时候，
快指针围绕着环走了一圈又回到了入口节点。

如何得到得到环中节点的个数？

利用快慢指针，找到环中的任意一节点，从该节点走一圈，并计数，当再次回到该节点的时候，便统计完了环中节点的个数。

 1 /*
 2  public class ListNode {
 3     int val;
 4     ListNode next = null;
 5 
 6     ListNode(int val) {
 7         this.val = val;
 8     }
 9 }
10 */
11 public class Solution {
12     public ListNode EntryNodeOfLoop(ListNode head)
13         {
14             ListNode pMeet = MeetingNode(head);
15             if(pMeet==null) return null;
16 
17             ListNode fast = head.next;
18                ListNode slow = head;
19             for(ListNode p = pMeet.next;p!=pMeet;p=p.next)
20                 fast = fast.next;
21 
22             while(slow!=fast){
23                 slow = slow.next;
24                 fast = fast.next;
25 
26             }
27             return fast;
28     }
29 
30 
31 
32    private ListNode MeetingNode(ListNode head){
33         if(head ==null|| head.next==null) return null;
34         ListNode slow = head;
35         ListNode fast = head.next.next;
36         while(slow!=fast){
37             slow = slow.next;
38             fast = fast.next.next;
39         }
40         return slow;
41     }
42 
43 
44 
45 
46 }

c++:20180729

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6         val(x), next(NULL) {
 7     }
 8 };
 9 */
10 class Solution {
11 public:
12     ListNode* EntryNodeOfLoop(ListNode* head)
13     {
14         
15         ListNode* meetNode= meeting(head);
16         if(meetNode==NULL) return NULL;
17         ListNode* fast = head;
18         ListNode* slow = head;
19         for(ListNode* p = meetNode;p!=meetNode;p=p->next)        
20             fast=fast->next;
21         
22         while(slow!=fast){
23             fast = fast->next;
24             slow = slow->next;
25         }
26         return fast;
27     }
28 
29     ListNode* meeting(ListNode* head){
30     if(head==NULL ||head->next==NULL) return NULL;
31         ListNode* fast = head->next->next;
32         ListNode* slow = head;
33         while(slow!=fast){
34             fast = fast->next->next;
35             slow = slow->next;
36         }
37     return fast;
38 }
39 };