Check if a linked list is a circular linked list

The problem, simply

You get the head of a linked list. Say true if the list is circular: the last box does not point to null, it points back to the head, so the boxes form a ring. Say false otherwise.

There are three kinds of lists you might get. A plain list that ends in null. A ring, where the tail points to the head. And a list with a loop somewhere in the middle, where the tail points back to some box that is not the head. Only the ring counts as circular.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk the list and keep a bag of every box you have stepped on, a hash set. Stop as soon as one of three things happens:

1. You reach null. It is a line, return false.
2. You reach the head again. It is a ring, return true.
3. You reach a box that is already in the bag, but it is not the head. There is a loop that skips the head, return false.

class Solution {
    public boolean isCircular(ListNode head) {
        if (head == null) return true;          // the GfG rule; ask your interviewer
        Set<ListNode> seen = new HashSet<>();
        ListNode curr = head;
        while (curr != null) {
            if (seen.contains(curr)) return curr == head;  // back at the head means a ring
            seen.add(curr);
            curr = curr.next;
        }
        return false;                           // fell off the end
    }
}

How long it takes: each box is visited once before we stop, O(n). Extra room: the bag can hold every box, O(n).

Way 2: the clever way

Use two runners on the list, a slow one that takes one step and a fast one that takes two. If the list ends, fast finds null first and we say false. If there is any loop, fast laps slow and they land on the same box.

A loop is not enough, though. We must know where the loop begins. Here is the magic part: put slow back on the head, leave fast where they met, and move both one step at a time. They meet again exactly at the box where the loop begins. The list is circular only if that box is the head.

1. Move slow by 1 and fast by 2 until fast hits null (return false) or they meet.
2. Put slow back on the head. Move both by 1 until they meet.
3. Return true if they meet on the head.

The same two runners on the sneaky list:

class Solution {
    public boolean isCircular(ListNode head) {
        if (head == null) return true;               // the GfG rule; ask your interviewer
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {                      // there is a loop
                slow = head;
                while (slow != fast) {               // walk both to where the loop begins
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow == head;                 // circular only if it begins at the head
            }
        }
        return false;                                // fast found the end
    }
}

How long it takes: fast catches slow within about two trips around the list, and the second phase walks at most n more steps, O(n). Extra room: two fingers, O(1).

Watch out for

• An empty list: decide the answer first. GeeksforGeeks says true.
• One box pointing to itself is circular. Both ways handle it: slow and fast meet on the head after one step.
• In the fast loop, check fast != null && fast.next != null before jumping two steps, or you get a null pointer crash on a plain list.
• Circular is not the same as "has a loop". A loop is anywhere; circular means the loop starts at the head.

What interviewers ask next

• Why does the second phase find the loop's first box? Say the tail before the loop has a boxes and slow walked a + b steps when they met. Fast walked twice that, so the extra a + b steps are whole laps of the loop. That means walking a more steps from the meeting point lands on the loop's first box, and so does walking a steps from the head.
• How long is the loop? After they meet, keep fast still and walk slow around until it comes back. Count the steps.
• Count the boxes of a circular list. Start at the head and walk with a do while loop until you are back at the head.
• Can you check it if you are allowed to change the list? Yes: flip arrows as you go, and you come back to the head if there is any loop. That is clever but wrecks the list, so it is rarely what they want.

Remember this

Grown-up words: the ring of kids is a circular linked list, a ring with a tail is a cycle that does not include the head, the bag of seen boxes is a hash set, and the two runners are Floyd's cycle detection, also called the tortoise and the hare.