leetcode--Linked List Cycle

Given a linked list, determine if it has a cycle in it.

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

/**
 * 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) {
        boolean hasCycle = true;
		if(head == null)
			hasCycle = false;
		else{
			ListNode first = head;
			ListNode second = head;
			do{
				if(second.next == null || second.next.next == null){
					hasCycle = false;
					break;
				}	
				else{
					first = first.next;
					second = second.next;
					second = second.next;
				}
			}while(first != second);
		}
		return hasCycle;
    }
}

The same method as above

/**
 * 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) {
       boolean hasCycle = false;
        if(head != null){
            ListNode speedOne = head, speedTwo = head;
            while(!hasCycle){
                if(speedTwo == null || speedTwo.next == null)
                    break;
                else{
                    speedTwo = speedTwo.next.next;
                    speedOne = speedOne.next;
                    hasCycle = (speedOne == speedTwo)? true : false;
                }
            }
        }
        return hasCycle;
    }
}

  

原文地址:https://www.cnblogs.com/averillzheng/p/3545282.html