[leetcode]Linked List Cycle II

新博文地址：[leetcode]Linked List Cycle II

 

http://oj.leetcode.com/problems/linked-list-cycle-ii/

 

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

 判断一个链表是否含有环，如包含，则返回环的起点。

这道题，有一种很高大上的解法，算法思想具体步骤有两步：（如何检测就不多说了）

1. Once a loop as been detected (step-3 above), move one of the pointers to the beginning (head) of the linked list. The second pointer remains where it was at the end of step-3.
2. Increment both pointers one node at a time. The node at which the two pointers meet will be the starting node of the loop!

  具体就是，

1.找到第一次相遇到的节点（http://huntfor.iteye.com/admin/blogs/2052045），快指针就指向该节点，慢指针重新指向头结点；

2. 然后这两个指针均每次走一步，则第二次相遇的节点即为头结点

具体的算法分析请移步

http://umairsaeed.com/2011/06/23/finding-the-start-of-a-loop-in-a-circular-linked-list/

代码实现起来也是非常简单的：

	public ListNode detectCycle(ListNode head) {
		ListNode meetNode = hasLoop(head);//判断是否有环，如有，则返回第一次相遇节点
		if(meetNode == null){
			return null;
		}
		ListNode slow = head;
		ListNode fast = meetNode;
		while(fast != slow){
			slow = slow.next;
			fast = fast.next;
		}
		return fast;		
	}