[LeetCode] 141. Linked List Cycle

 

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

Linked List Cycle - LeetCode

문제 유형 : 연결 리스트, 투 포인터

문제 난이도 : Easy

 

문제

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.

 

연결리스트의 헤드 head가 주어진다. 이 연결리스트가 사이클이 존재하는지 알아내시오.

사이클의 pos는 연결 리스트의 마지막 노드에서 다음 노드로의 인덱스를 가리킨다. 이는 연결리스트의 파라미터로 주어지지 않는다.

 

풀이

해시 테이블을 만들어서 노드를 방문하면 1을 누적시킨다. 만약 key(노드)의 value(횟수)가 1보다 크면, 다시 돌아왔다는 뜻이므로 true를 반환한다. 끝내 탐색이 끝나면 사이클이 없다는 뜻이므로 false를 반환한다.

 

코드

C++

/**
 * 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> table;
        auto curr = head;

        while(curr != nullptr) {
            table[curr]++;
            if(table[curr] > 1) {
                return true;
            }
            curr = curr -> next;
        }

        return false;
    }
};

 

 

 

 

++(2024. 3.6 추가)

토끼와 거북이와 같은 알고리즘을 발견했습니다. 공간복잡도가 O(1)입니다.

한 노드는 두 칸, 하나는 한 칸씩 움직이면서 한 번이라도 겹치면 사이클이 맞습니다.

/**
 * 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) {
        auto fast = head;
        auto slow = head;

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

            if(fast == slow) return true;
        }

        return false;
    }
};