leetcode 142) Linked List Cycle II

LV. Medium 🧐

https://leetcode.com/problems/linked-list-cycle-ii/

Linked List Cycle II - LeetCode

 

문제

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

 

Example 1:

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

Example 2:

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

Example 3:

Input: head = [1], pos = -1
Output: no cycle
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.

 

문제 해결법

만약 circle이 존재하면 head->next로 계속 이동하면 무한 루프이다!

이를 체크하기 위해 ListNode의 주소을 저장해서 중복된 값이 나오면 그 주소를 리턴하는 방식으로 풀었다.

중복되지 않은 값을 저장한다는 생각에 며칠 전 공부한 unordered_map이 생각났다.

map를 사용하면 key만 의미 있는 데이터가 들어가 value는 메모리 낭비만 하게 되지만..

중복 없이 저장하는 법을 몰라.. unordered_map <ListNode의 주소, bool : 의미 없는 데이터> 형식으로 저장했다.

unordered_map를 통해 메모리 낭비는 심하지만 쉽게 해결!

 

해결 코드

//Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
 
class Solution {
public:
	ListNode *detectCycle(ListNode *head) {
		unordered_map<ListNode *, bool> m;
		ListNode *temp;

		temp = head;
		while (temp) {
			auto it = m.find(temp);
			if (it != m.end())
				return temp;
			m[temp] = true;
			temp = temp->next;
		}
		return 0;
	}
};