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

Analysis: have two pointer. one goes at one step at a time, the other goes at two step at a time. if two pointers meet with each other, then there is a loop. The coding is very simple.

  public boolean hasCycle(ListNode head) {  
        if (head == null || head.next == null){
            return false;
        }

        ListNode oneStep = head.next;
        ListNode twoStep = head.next.next;

        if (twoStep == null){
            return false;
        }

        while (twoStep.next != null && twoStep.next.next != null){
            if (oneStep == twoStep){
                return true;
            }

            oneStep = oneStep.next;
            twoStep = twoStep.next.next;
        }

        return false;
    }