Linked List Cycle

Posted on

 

/* Given a linked list, determine if it has a cycle in it. */

public class Solution {

public boolean hasCycle(ListNode head) {

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


A nice trick about Linked List is the slow and fast pointers/runners. If both runners start at the same nodes, sooner or later they’ll meet at a specific node with the existence of the cycle. If there’s no cycle, then the fast runner will encounter null finally. Since fast.next also needs to visit its own next node, so the null check is also needed for fast.next. This case must be included in the condition of ending while-loop.

Be careful about the edge cases. The null list or single node list request the specific null check. Also, when there are only two nodes in the list, the slow and fast runners start at the same node. So the condition check of slow == fast is put after they both go forward their steps (I used “slow = head; fast = head”, if using “slow = head; fast = head.next”, will be different).

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s