Offer23（环形链表的头节点）

发表于 | 分类于 ，

题目：

　　给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路：

　　此题包含两个问题：1.判断链表中是否有环；2.若有环，找出环的入口节点。对于此问题，无论是判断是否有环还是找入口节点，都可以使用哈希表（Set）
解出，但需要O(n)的空间复杂度。现在来优化空间复杂度。判断是否有环可以使用快慢双指针（慢指针一次走一步，快指针一次走两步），若有环则两指针必定
会相遇。对于寻找入口节点，需要进行推导。假设环外节点数为F，环内节点数为C，当慢指针走到入口节点处时，慢指针走了F步，同样快指针在环内一定走了F
步，若慢指针继续走C-F步，则两指针必定相遇（快指针走2（C-F）步），即两指针必定相遇在C-F处，此时再定义一个指针指向头节点，当头节点指针与相遇节点
指针相遇时，相遇的节点即为入口节点。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 public ListNode EntryNodeOfLoop(ListNode pHead)
 {
     ListNode fastNode = pHead;
     ListNode slowNode = pHead;
     while(fastNode != null && fastNode.next != null) {
     	fastNode = fastNode.next.next;
     	slowNode = slowNode.next;
     	if (fastNode == slowNode) {
	while(pHead != fastNode) {
		pHead = pHead.next;
		fastNode = fastNode.next;
	}
	return fastNode;
}
     }
     return null;
 }

复杂度分析：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。