Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 연결 리스트 사이클 II — 플로이드 알고리즘으로 사이클 시작 노드 찾기

문제 소개

연결 리스트(Linked List)가 주어졌을 때, 이 리스트 안에 사이클(cycle), 즉 순환 구조가 존재하는지 판별하고, 존재한다면 사이클이 시작되는 노드를 찾아내는 것이 이 글의 목표입니다.

사이클의 위치는 정수형 변수 pos로 표현합니다. pos는 리스트의 꼬리(tail) 노드가 다시 연결되는 위치를 가리키며, pos = -1이면 사이클이 없음을 의미합니다. 예를 들어 연결 리스트가 [5, 3, 2, 0, -4, 7]이고 pos = 1이라면, 마지막 노드(값 7)가 두 번째 노드(값 3)에 연결되어 순환이 형성됩니다.

여기서 중요한 제약 조건은 리스트 자체를 수정할 수 없다는 점입니다. 따라서 노드의 값이나 포인터를 변경하지 않고, 오직 포인터 이동만으로 문제를 해결해야 합니다.

해결 접근 방식: 플로이드 순환 감지 알고리즘

이 문제는 플로이드 순환 감지 알고리즘(Floyd's Cycle Detection Algorithm), 흔히 '거북이와 토끼(Tortoise and Hare)' 기법이라 불리는 방법으로 풀 수 있습니다. 핵심은 서로 다른 속도로 움직이는 두 포인터를 활용하는 것입니다.

  • slow(느린 포인터) — 한 번에 한 노드씩 이동
  • fast(빠른 포인터) — 한 번에 두 노드씩 이동

사이클이 존재한다면 빠른 포인터는 결국 느린 포인터를 따라잡게 됩니다. 두 포인터가 만나는 시점에서 사이클의 존재 여부를 확정할 수 있으며, 이후 한 포인터를 head로 되돌려 다시 만나는 지점이 곧 사이클의 시작 노드가 됩니다.

알고리즘 단계

  1. slow와 fast를 모두 head로 초기화합니다.
  2. slow, fast, fast->next가 모두 유효한 동안 아래를 반복합니다.
    • slow는 한 칸, fast는 두 칸 전진합니다.
    • slow == fast이면 반복을 종료합니다.
  3. fast가 NULL이거나 fast->next가 NULL이면 사이클이 없으므로 NULL을 반환합니다.
  4. slow == fast라면 사이클이 존재하는 것이므로,
    • slow를 head로 되돌립니다.
    • 두 포인터가 같아질 때까지 한 칸씩 함께 전진합니다.
  5. slow를 반환합니다. 이것이 바로 사이클의 시작 노드입니다.

그렇다면 왜 이 방법이 작동할까요? 두 포인터가 처음 만난 지점부터 사이클 시작 노드까지의 거리와, head부터 사이클 시작 노드까지의 거리가 수학적으로 동일하기 때문입니다. 따라서 slow를 head로 옮긴 뒤 두 포인터를 같은 속도로 전진시키면, 반드시 사이클 시작 노드에서 다시 만나게 됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class ListNode{
    public:
        int val;
        ListNode *next;
        ListNode(int data){
            val = data;
            next = NULL;
        }
};
ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return head;
}
ListNode *get_node(ListNode *head, int pos){
    ListNode *ptr = head;
    if(pos != -1){
        int p = 0;
        while(p < pos){
            ptr = ptr->next;
            p++;
        }
        return ptr;
    }
    return NULL;
}
class Solution {
    public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(slow && fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)break;
        }
        if(!fast || !fast->next)return NULL;
        if(slow == fast){
            slow = head;
            while(slow!=fast){
                slow = slow->next;
                fast = fast->next;
            }
        }
        return slow;
    }
};
main(){
    Solution ob;
    vector<int> v = {5,3,2,0,-4,7};
    ListNode *head = make_list(v);
    int pos = 1;
    ListNode *lastNode = get_node(head, v.size() - 1);
    lastNode->next = get_node(head, pos);
    cout << "꼬리 노드가 연결된 노드의 값:" << ob.detectCycle(head)->val;
}

입력

[5,3,2,0,-4,7]
1

출력

꼬리 노드가 연결된 노드의 값:3

복잡도 분석

  • 시간 복잡도: O(n) — 두 포인터 모두 최대 n번 이동하므로 선형 시간 안에 해결됩니다.
  • 공간 복잡도: O(1) — 추가적인 메모리 없이 포인터 두 개만 사용합니다.