**source:**https://leetcode.com/problems/linked-list-cycle/**C/C++**

**Solution to LeetCode**problem

**141**.

**Linked List Cycle**.

## Problem

Given `head`

, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next`

pointer. Internally, `pos`

is used to denote the index of the node that tail’s `next`

pointer is connected to. **Note that pos is not passed as a parameter.**

Return `true`

*if there is a cycle in the linked list*. Otherwise, return `false`

.

## Examples

**Example 1:**

Input:head = [3,2,0,-4], pos = 1

Output:true

Explanation:There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

**Example 2:**

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

Output:true

Explanation:There is a cycle in the linked list, where the tail connects to the 0th node.

**Example 3:**

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

Output:false

Explanation:There is no cycle in the linked list.

## Constraints

- The number of the nodes in the list is in the range
`[0, 10`

.^{4}] `-10`

^{5}<= Node.val <= 10^{5}`pos`

is`-1`

or a**valid index**in the linked-list.

## Solution

I can think of 2 different solutions.

- Using a hashmap
- Add the pointer address of the current node to the hashmap.
- If
`node->next`

address is already in the hashmap then there is a cycle. - Move to the next node and repeat.

- Using two pointers
- Both pointers start at
`head`

. - One pointer will move one node at the time (i.e.
`node->next`

), and the other pointer two nodes (i.e.`node->next->next`

). - As long as the two pointers are not
`ptrnull`

,**if there is a cycle, both pointers will be equal at some point**. - If any pointer becomes
`nullptr`

then there is NO cycle.

- Both pointers start at

### Solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *ptr = head;
unordered_map<ListNode*, bool> hash_table;
hash_table[head] = 1;
while (ptr) {
if (hash_table[ptr->next])
return true;
hash_table[ptr->next] = true;
ptr = ptr->next;
}
return false;
}
};

### Solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution
{
public:
bool hasCycle(ListNode *head) {
ListNode* f = head;
ListNode* s = head;
while (f && f->next) {
s = s->next;
f = f->next->next;
if (f == s)
return true;
}
return false;
}
};