Leet Code - 141. Linked List Cycle(C++)

예제: Linked List Cycle

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

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.

Example 1:

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.

Example 2:

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

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

풀이

cycle이 있는 linked list인지 묻는 문제이다.
특이한게, 문제에서는 input에 사이클의 인덱스인 pos가 붙어 나오는데 실제 문제에서 input으로 들어오지도 않고(들어오면 바로 답을 찾을테니).. 무슨 의미인지 모르겠다.

필자는 처음에 unordered_map을 사용해서 ListNode의 주소를 저장한 후, list를 따라가며 주소가 이전에 저장된 주소일 경우 바로 true를 리턴하도록 로직을 설계했다. map에 넣고 검색하는 과정이 있어서 그런지, 속도가 그렇게 빠르지 않았다.

다른 풀이들을 보니, fast와 slow라는 포인터를 선언하여, fast는 두 번씩 이동, slow는 한 번씩 이동하여 fast와 slow가 같은지 보는 방식을 사용했다. 결국 모든 head의 경우를 검색할 수 있고, 빠르게 다음 노드를 검색할 수 있으므로 속도가 빨랐다.

전체적인 소스코드는 아래와 같다.

소스 코드

/* CASE1 */
/**
 * 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) {
		unordered_map<ListNode*, int> um;

		while (head != NULL) {
			if (um[head] > 0) return true;

			um[head]++;
			head = head->next;

		}

		return false;
	}
};

/* CASE2 */
/**
 * 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* slow = head;
		ListNode* fast = head;

		while (fast && fast->next) {
			slow = slow->next;
			fast = fast->next->next;

			if (slow == fast)
				return true;
		}

		return false;
	}
};

풀이 후기

CASE2번의 방법.. 참 쉬우면서도 생각해내기 어려운 방법이다.
다들 어찌도 알고리즘 머리가 이렇게 좋은지 모르겠다. 알고리즘은 재능의 영역이라고 하는데, 본인도 그 재능이 있을 것이라 굳게 믿으며 오늘도 문제를 풀 뿐이다.