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 | Input: head = [3,2,0,-4], pos = 1 |

1 | Input: head = [1,2], pos = 0 |

1 | Input: head = [1], pos = -1 |

**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 | [3,2,0,-4] pos = 1 true |

### Hash Set

Use `Set<ListNode>`

instead of `Set<Integer>`

.

1 | public boolean hasCycle(ListNode head) { |

**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 | // 1 2 3 4 5 |

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 | // 1 2 3 4 5 |

**Note:** So many corner cases.

My originally bad code (using `flag`

):

1 | public boolean hasCycle(ListNode head) { |

**Improvement:**

1 | public boolean hasCycle(ListNode head) { |

**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 | public boolean hasCycle(ListNode head) { |

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