# 142. Linked List Cycle II
Difficulty: Medium

## Solution

/**
*** Author: R-CO
*** E-mail: [e-mail]
*** Date: 2020-09-25
**/

#define FLOYD_ALGORITHM 1

#if (FLOYD_ALGORITHM == 0)

#include <unordered_set>
using namespace std;

#endif

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(nullptr) {}
};

#if (FLOYD_ALGORITHM == 0)

class Solution {
public:
	ListNode *detectCycle(ListNode *head) {
		unordered_set<ListNode*> node_set;

		while (head != nullptr) {
			if (node_set.count(head) > 0) {
				return head;
			}

			node_set.insert(head);
			head = head->next;
		}

		return nullptr;
	}
};

#else

class Solution {
public:
	ListNode *detectCycle(ListNode *head) {
		if (head == nullptr) {
			return nullptr;
		}
		
		ListNode *rabbit = head->next;
		ListNode *tortoise = head;

		while (rabbit != nullptr && rabbit != tortoise) {
			if (rabbit->next == nullptr) {
				break;
			}

			tortoise = tortoise->next;
			rabbit = rabbit->next->next;
		}

		if (rabbit != tortoise) {
			return nullptr;
		}

		ListNode *node_1 = head;
		ListNode *node_2 = rabbit->next;

		while (node_1 != node_2) {
			node_1 = node_1->next;
			node_2 = node_2->next;
		}
		ListNode *cycle_begin_position = node_1;

		return cycle_begin_position;
	}
};

#endif

## Result

Success
Details
Runtime: 8 ms, faster than 96.23% of C++ online submissions for Linked List Cycle II.
Memory Usage: 7.7 MB, less than 63.63% of C++ online submissions for Linked List Cycle II.

###### tags: `LeetCode-Medium` `C++`