Reference: LeetCode
Difficulty: EasyTwo Pointers

My Post: Java Solution with Explanations and Illustrations

Problem

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

Note:

  • To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
  • There could be duplicates.

Example: 

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

1
2
3
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
1
2
3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up: Can you solve it using $O(1)$ (i.e. constant) memory?

  • Yes. Use two pointers or modify the next.

Analysis

Note: In terms of duplicate nodes, they are different node objects. So it is okay to use hashCode() and ==.

Test Case:

1
2
3
[3,2,0,-4]  pos = 1   true
[1,2]       pos = 0   true
[1]         pos = -1  false

Hash Set

Use Set<ListNode> instead of Set<Integer>.

1
2
3
4
5
6
7
8
9
10
11
12
public boolean hasCycle(ListNode head) {
  ListNode p = head;
  Set<ListNode> seen = new HashSet<>();
  while (p != null) {
    if (seen.contains(p)) {
      return true;
    }
    set.add(p);
    p = p.next;
  }
  return false;
}

Time: $O(N)$.
Space: $O(N)$.

Two Pointers

The space complexity can be reduced to $O(1)$ by considering two pointers at different speed. A slow pointer and a fast pointer. The slow pointer moves one step at a time while the fast pointer moves two steps at a time. If there is no cycle in the list, the fast pointer will eventually reach the end and we can return false in this case.

  • No cycle
    The fast pointer reaches the end first and the run time depends on the list’s length, which is $O(N)$.
  • Cycle exists
    • Non-cyclic part:
      • The slow pointer takes non-cyclic length steps to enter the cycle. The length is $L1$.
    • Cyclic part:
      • When two pointers enter into the cycle, it will take:
      • (distance between two pointers (at most $C$) / difference of speed) moves for the fast pointer to catch up with the slow runner.

Therefore, the worst case runtime is $O(L1 + C)$, which is $O(N)$.

Why will the fast pointer eventually meet the slow pointer?

Consider the one-step case:

1
2
3
4
5
//  1   2   3   4   5
//  f   s
//      --->s
//  ------->f

If the fast pointer is two steps behind the slower runner, this case will change into the one-step case above (each time the distance decreases by $1$):

1
2
3
4
5
//  1   2   3   4   5
//  f       s
//          --->s
//              --->s
//  ------->f------>f

Note: So many corner cases.

My originally bad code (using flag):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean hasCycle(ListNode head) {
  ListNode slow = head;
  ListNode fast = head;
  boolean flag = false;
  while (slow != null && fast != null && fast.next != null) {
    if (slow == fast) { // skip the beginning
      if (flag) return true;
      else      flag = true;
    }
    slow = slow.next;
    fast = fast.next.next;
  }
  return false;
}

Improvement:

1
2
3
4
5
6
7
8
9
10
11
12
public boolean hasCycle(ListNode head) {
  ListNode slow = head;
  ListNode fast = head;
  while (fast != null && fast.next != null) { // right-leaning
    slow = slow.next;
    fast = fast.next.next;
    if (fast == slow) {
      return true;
    }
    return false;
  }
}

Time: $O(N)$
Space: $O(1)$

Mark Node

By Argondey: I used a slightly faster destructive approach. I created a new node called “mark” and iterated through the list, setting the next value of each node to the mark node. When reaching the new node the first thing I did was check if the node is the mark node. If it ever is the mark node, we have looped. Brilliant!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean hasCycle(ListNode head) {
  ListNode mark = new ListNode(0);
  ListNode p = head;
  while (p != null) {
    if (p == mark) {
      // or p.next == null and return p to get the node
      return true;
    }
    ListNode nextTemp = p.next;
    p.next = mark;
    p = nextTemp;
  }
  return false;
}

Time: $O(N)$
Space: $O(1)$