142. Linked List Cycle II.md

142. Linked List Cycle II

Problem

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

Note: Do not modify the linked list.

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

tag:

Solution

参考，141. Linked List Cycle 解题报告

java

    public boolean hasCycle(ListNode head) {
        ListNode f = head, s = head;
        while(s!=null&&s.next!=null) {
            s = s.next.next;
            f = f.next;
            if(s==f) return true;
        }
        return false;
    }

go

func DetectCycle(head ListNode) *ListNode {
	s, f := &head, &head
	if s == nil || s.next == nil {
		return nil
	}
	for s != nil && f.next != nil {
		s = s.next
		f = f.next.next
		if f == s {
			break
		}
	}
	if f != s {
		return nil
	}
	f = &head
	for f != s {
		f = f.next
		s = s.next
	}
	return f
}