Linked list cycle

Given a linked list, determine if it has a cycle in it. (Without using eatra space)

//Solution: define two pointers, one moves one step each time while the other moves two steps. If the second one catches the first at some point, return true.

Java:

/** 
 * Definition for singly-linked list. 
 * class ListNode { 
 *     int val; 
 *     ListNode next; 
 *     ListNode(int x) { 
 *         val = x; 
 *         next = null; 
 *     } 
 * } 
 */ 
public class Solution { 
    public boolean hasCycle(ListNode head) { 
        if(head==null) 
            return false; 
        ListNode first = head; 
        ListNode second = head; 
        while (first.next!=null && second.next!=null && second.next.next!=null){               //remember to check second.next first 
            first = first.next; 
            second = second.next.next; 
            if(first==second) 
                return true; 
        } 
        return false; 
  
    } 
}

Python:

# Definition for singly-linked list. 
# class ListNode: 
#     def __init__(self, x): 
#         self.val = x 
#         self.next = None 
 
class Solution: 
    # @param head, a ListNode 
    # @return a boolean 
    def hasCycle(self, head): 
        if head==None: 
            return False 
        first = head 
        second = head 
        while first.next!=None and second.next!=None and second.next.next!=None: 
            first = first.next 
            second = second.next.next 
            if first==second: 
                return True 
        return False

Linked list cycle

原文：http://www.cnblogs.com/cs-jack-cheng/p/4110349.html