Given a linked list, find out if it has a cycle in it.

A linked list cycle looks like this:

If there is no cycle in it, return false.

The idea is pretty simple. We just need a slow node which moves one step at a time, and a fast node which moves two steps at a time. If there is a cycle in the linked list, the slow node will eventually catch up with the fast node. Let's take a look at the solution:

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

You just need to make sure that the slow.next != null and fast.next.next != null. When slow == fast, simply return true.

Follow up: if a cycle is found, can you return the node where the cycle begins?

In the first part, we can already determine whether a linked list has cycle or not. Now, we need to find out where the cycle begins. Let's find out!

Let's use the example above.

When the slow and fast node meets at the point p, slow node has traveled a + b (2 steps) distance while fast node has traveled a + b + c + b (4 steps) distance.

Since the travel distance of fast node is twice the travel distance of slow node, we can safely conclude that a + 2b + c = 2 (a + b) which we then can simplify to a = c.

Once we can conclude that the travel distance a is actually the same as c, we can begin to move both head node and slow node forward, they will meet at point q where the cycle begins.

Here's the solution:

    public ListNode detectCycle(ListNode head) {   
    
        if(head == null){
            return null;
        } 
        
        ListNode slow = head;
        ListNode fast = head;
        
        while(slow.next != null && fast.next != null && fast.next.next != null){
            
            slow = slow.next;
            fast = fast.next.next; 
            if(slow == fast){
                ListNode curr = head;
                while(curr != slow){
                    curr = curr.next;
                    slow = slow.next;
                }
                return curr;                
            }       
        }  
        return null;     
    }

---

There we have it!

Post was published on 31 Jan 2020, last updated on 31 Jan 2020.

Like the content? Support the author by paypal.me!