首页 > itarticle > linked list cycle

linked list cycle

admin 11月 11, 2020 0

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


	> File Name: LinkedListCycle.java
	> Author: Yao Zhang 
	> Mail: [email protected] 
	> Created Time: Fri 20 Nov 11:42:04 2015
 ************************************************************************/

public class {
	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;
    }
}