学步园

貌似国内面试经常问得题目，以前没遇到过。。

思路：

1： 两个指针，一个一次走两格，一个一次走一个。相遇了证明有环。

2： 然后因为快的那个总是比慢的那个走快一步，当他们相遇后，再走k步（k是circle的结点数量）后，他们会再相遇，从而求出circle结点数量。

3： 最后再设置两个指针（都是一次走一步），但一开始一个比另外一个领先k步，那么它们就会刚好在环的起点相遇。。

但是偶在初始化那里接连犯了好几个错误。

该题目的另外一个变形：“两个链表，求相交的第一个节点”。

import java.util.*;

  class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
         val = x;
         next = null;
    }
  }

public class Solution {
	
	ListNode dCycle(ListNode head)
	{
		if(head == null || head.next == null)
			return null;
		ListNode pSlow,pFast;
		pSlow = head;
		pFast = head.next;
		
		while(pFast.next != null && pFast.next.next != null && pFast != pSlow)
		{
			pFast = pFast.next.next;
			pSlow = pSlow.next;
		}
		
		if(pFast.next == null || pFast.next.next == null)
			return null;
		return pFast;
	}
	
	int CycleN(ListNode cnode)
	{
		ListNode pFast,pSlow;
		pSlow = cnode.next;
		pFast = cnode.next.next;
		
		int k = 1;
		while(pFast != pSlow)
		{
			pFast = pFast.next.next;
			pSlow = pSlow.next;
			k++;
		}
		
		return k;
	}
	
    public ListNode detectCycle(ListNode head) {
    	
    	if(head == null) return null;
    	else if(head.next == null) return null;
    	
        ListNode cNode = dCycle(head);
        
        if(cNode == null) return null;
        
        int iCycleN = CycleN(cNode);
        
        ListNode pAdvNode = head;
        ListNode pNode = head;
        
        for(int i=0;i<iCycleN;i++){
        	pAdvNode = pAdvNode.next;
        }
        
        while(pAdvNode != pNode)
        {
        	pAdvNode = pAdvNode.next;
        	pNode = pNode.next;
        }
        
        return pNode;
    }
    
    
    
    
    public static void main(String[] args)
    {
    	Solution sol = new Solution();
    	ListNode n1,n2,n3;
    	n1 = new ListNode(1);
    	n2 = new ListNode(2);
    	n3 = new ListNode(3);

    	n1.next = n2;
    	n2.next = n3;
    	
    	ListNode bNode = sol.detectCycle(n1);
    	System.out.println(bNode);
    }

}