[LeetCode] 141. Linked List Cycle

LeetCode - 136. Single Number 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/linked-list-cycle

풀이

연결리스트를 이루는 원소 배열과 사이클이 이루어지는 인덱스(pos)가 주어진다.

(연결리스트의 첫 번째 원소의 인덱스를 0으로 생각하면 된다.)

주어진 연결리스트에 사이클이 존재하는지 확인하여 true/false를 반환하는 문제이다.

해시를 사용하여 접근하기

이 문제를 해결하기 위해 해시 자료구조를 사용하는 것을 생각해볼 수 있다.

unordered_set<ListNode*> us;를 정의하여

1. 연결리스트를 순회하면서 포인터 주소가 이미 추가되었는지 확인한다.
   1. 추가되지 않았다면 포인터 주소를 추가한다.
   2. 이미 추가된적이 있다면 사이클이 발생하였다는 의미이고, 곧바로 true를 반환하여 함수를 종료한다.

소스코드

/**
 * 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_set<ListNode*> us;
        while (head != nullptr) {
            if (us.find(head) != us.end()) {
                return true;
            }
            us.insert(head);
            head = head->next;
        }
        return false;
    }
};

플로이드의 사이클 탐지 알고리즘

Floyd’s Cycle Finding Algorithm

위에서 해시를 이용한 풀이에서는 포인터 위치를 하나씩 옮겼다. (head = head->next)

그렇다면 포인터를 하나씩 이동하지 않고 2개씩 이동하면 어떨까?

플로이드의 사이클 탐지 알고리즘의 핵심 개념은 다른 속도로 이동하는 두 개의 포인터를 활용하여 연결리스트를 탐색하였을 때, 연결리스트가 사이클을 형성하고 있다면 언젠가는 같은 노드를 가리키게 된다는 것이다.

• 다음 포인터로 이동 : list_1 = list_1->next
• 다음 포인터의 포인터로 이동 : list_2 = list_2->next->next

※ 두 칸씩 이동하므로 nullptr을 확인할 때 list_2->next 값이 nullptr인지도 함께 확인해야 한다.

소스 코드

/**
 * 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 *list_1 = head, *list_2 = head;
        while (list_1 != nullptr && list_2 != nullptr && list_2->next != nullptr) {
            list_1 = list_1->next;
            list_2 = list_2->next->next;
            if (list_1 == list_2) {
                return true;
            }
        }
        return false;
    }
};