首页 > 代码库 > Linked List Cycle II

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?

方法

    public ListNode detectCycle(ListNode head) {
    	if (head == null || head.next == null) {
    		return null;
    	}
    	ListNode first = head;
    	ListNode second = head;
    	while (second != null) {
    		second = second.next;
    		if (second != null) {
    			second = second.next;
    		} else {
    			return null;
    		}
    		first = first.next;
    		if (second == first) {
    			break;
    		}
    	}
    	if (second == null) {
    		return null;
    	} else {
    		ListNode node = head;
    		while(second != node){
    			second = second.next;
    			node = node.next;
    		}
    		return node;
    	}
    	
    }