Find Loops In Linkedlist

Find loops in LinkedList

Naive Thinking:用一快一慢两个指针找出是否有loop。着相当于是找圈的起点的简化版。 加强版的见Intersection of Two Linked Lists


算法复杂度O(n)。

class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null;
    }
}

public class Solution{

    public static void main(String args[]){
        ListNode l1 = new ListNode(0);
        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(2);
        l1.next = l2;
        l2.next = l3;
        l3.next = l2;
        Solution s = new Solution();
        System.out.println(s.hasLoop(l1));
    }

    public boolean hasLoop(ListNode head){
        ListNode slow = head, fast = slow;
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
            if(fast==null) break;
            fast = fast.next;
            if(slow==fast) return true;
        }
        return false;
    }
}