Leetcode and Lintcode

Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Example
Given -21->10->4->5, tail connects to node index 1, return true

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

Solution:

This is an easy problem. Just use two pointers to point to head.
One pointer go twice speed of the second pointer.
If they meet before the fast touch the end of the list, return true;
Else return false;

Leetcode link
Lintcode link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*************************************************************************
	> File Name: LinkedListCycle.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Fri 20 Nov 11:42:04 2015
 ************************************************************************/

public class LinkedListCycle{
	public boolean hasCycle(ListNode head) {
        if (head == null)
            return false;
            
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            
            if (slow == fast)
                return true;
        }
        
        return false;
    }
}