题目描述
一个链表中包含环，请找出该链表的环的入口结点。
解题思路
解决这个问题的第一步是如何确定一个链表中包含环。可以定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个一次走两步。如果走得快的指针走到了链表的末尾都没有追上第一个指针，那么链表就不包含环。反之则可得到环中的一个节点。
第二步是如何找到环的入口。还是可以用两个指针P1和P2指向链表的头结点，如果链表中的环有n个节点，则指针P1先在链表上向前移动n步，然后两个指针依次同时向前移动一步。当P2指向环的入口节点时，P1已经围绕着环走了一圈，又回到了入口节点。
剩下的问题是如何得到环中节点的数目。可以从第一步得到的环中节点开始每次走一步，计数走的步数直到它又回到原来的位置，就可以得到环中节点数了。
代码
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* pHead) 13 { 14 int len = LenOfLoop(pHead); 15 if(len == 0) 16 return NULL; 17 else{ 18 ListNode* first = pHead; 19 ListNode* second = pHead; 20 while(len-- > 0) 21 first = first->next; 22 while(first != second){ 23 first = first->next; 24 second = second->next; 25 } 26 return first; 27 } 28 } 29 int LenOfLoop(ListNode* pHead){ //得到环的长度 30 ListNode* first = pHead->next; 31 if(first != NULL) 32 first = first->next; 33 ListNode* second = pHead; 34 while(first != NULL){ //first每次走两步，second走一步，找到两者相等的节点即为环中节点 35 if(first == second){ 36 break; 37 } 38 else{ 39 first = first->next; 40 if(first != NULL) 41 first = first->next; 42 second = second->next; 43 } 44 } 45 if(first != NULL){ 46 ListNode* loop = first; 47 int len = 1; 48 while(loop != first->next){ 49 first = first->next; 50 len++; 51 } 52 return len; 53 } 54 else 55 return 0; 56 } 57 };
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
