Loop in List(链表中的圈)

Q： 给定一个linked list， 如何判断这个linked list 中是否有一个loop。 例如如下图：

链表的一个节点定义如下：

struct ListNode {int data;ListNode *next;
};

使用两个指针pFast和pSlow， 均初始化为指向链表头。 一个指针一次向前移动1个节点，  另一个指针一次向前移动两个节点。  也就是说pFast指针向前移动到的速度是pSlow的两倍。  如果移动快的pFast指针和移动慢的pSlow指针相遇了， 就表明list中有一个loop， 也就是pFast在转圈圈。 否则， 没有loop的话， 那么pFast 必然移动到list 的尾部。 程序如下：

bool HasLoop(ListNode *pHead) {if(pHead == NULL) return false;ListNode* pSlow = pHead -> next;if(pSlow == NULL)return false;ListNode* pFast = pSlow -> next;while(pFast != NULL && pSlow != NULL) {if(pFast == pSlow)return true;pSlow = pSlow -> next;pFast = pFast -> next;if(pFast != NULL)pFast = pFast -> next;}return false;
}

分析：  两个指针初始化链表头。 如果loop中有n个节点， 那么我们设定第一个指针先向前移动n个节点。 然后这两个指针以相同的步伐向前移动。 当第二个指针到达the entry of the loop， 第一个指针已经沿着这个loop一圈， 再次回到loop 的entry node，

例如下图：

如上图， 指针P1和指针P2首先初始化为指向链表头的节点。 由于loop中有四个节点，  所以P1 先走四步。 之后P1， P2在同时向前一次一个节点的走。

在本例中， 再移动两步， P1和P2就在loop的entry node 相遇。

问题来了， 如何知道loop的节点数目？？？？

参考第一问， 我们定义了两个指针， 这两个指针最终会在loop中的某个节点相遇。我们在接下来， 从相遇的节点处， 停止移动节点pFast, 然后一步一个节点的移动pSlow， 那么pSlow最终再次返回到meeting node 出所经过的节点数就是loop的节点数目。 程序如下：

ListNode* meetingNode(ListNode *pHead) {if(pHead == NULL) return false;ListNode* pSlow = pHead -> next;if(pSlow == NULL)return NULL;ListNode* pFast = pSlow -> next;while(pFast != NULL && pSlow != NULL) {if(pFast == pSlow)return pFast;pSlow = pSlow -> next;pFast = pFast -> next;if(pFast != NULL)pFast = pFast -> next;}return NULL;
}

ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode* meetingNode = MeetingNode(pHead);if(meetingNode == NULL)return NULL;// get the number of nodes in loopint nodesInLoop = 1;ListNode* pNode1 = meetingNode;while(pNode1->next != meetingNode){pNode1 = pNode1->next;++nodesInLoop;}// move pNode1pNode1 = pHead;for(int i = 0; i < nodesInLoop; ++i)pNode1 = pNode1->next;// move pNode1 and pNode2ListNode* pNode2 = pHead;while(pNode1 != pNode2){pNode1 = pNode1->next;pNode2 = pNode2->next;}return pNode1;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！