[7. 연결리스트] 7.3 사이클이 존재하는지 확인하기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

https://msugi.tistory.com/47

[7. 연결리스트] 7.0 연결리스트 기초 작업

연결리스트 문제를 풀기전 LinkedList를 위와 같이 직접 구현했다. 위 LikedList를 이용하여 문제를 풀 예정이다.

---

Q 7.3 사이클이 존재하는지 확인하기

단순 연결리스트의 사이클이 존재하는지 확인하는 프로그램을 작성하라.

---

해당 문제의 소스코드와 결과는 다음과 같다.

// 7.3 사이클이 존재하는지 확인하기#include "LinkedList.h"
 
Node<int>* HasCycle(const List<int>& head) // 사이클의 길이를 계산
{
    Node<int>* fast = head.HeadNode;
    Node<int>* slow = head.HeadNode;
 
    while (fast && fast->NextNode)
    {
        slow = slow->NextNode;
        fast = fast->NextNode->NextNode;
        if (slow == fast)
        {
            int CycleLen = 0;
            do
            {
                CycleLen++;
                fast = fast->NextNode;
            } while (slow != fast);
            auto CycleLen_iter = head.HeadNode;
            while (CycleLen--)
            {
                CycleLen_iter = CycleLen_iter->NextNode;
            }
            auto iter = head.HeadNode;
            while (iter != CycleLen_iter)
            {
                iter = iter->NextNode;
                CycleLen_iter = CycleLen_iter->NextNode;
            }
            return iter;
        }
    }
    return nullptr;
}
 
Node<int>* HasCycle_2(const List<int>& head) // 사이클의 길이는 계산 x
{
    Node<int>* fast = head.HeadNode;
    Node<int>* slow = head.HeadNode;
 
    while (fast && fast->NextNode && fast->NextNode->NextNode)
    {
        slow = slow->NextNode;
        fast = fast->NextNode->NextNode;
 
        if (slow == fast)
        {
            slow = head.HeadNode;
            while (slow != fast)
            {
                slow = slow->NextNode;
                fast = fast->NextNode;
            }
            return slow;
        }
    }
    return nullptr;
}

바깥 루프가 방문했던 노드를 안쪽 루프가 재방문했을때 사이클이 존재한다고 할 수 있으므로 해당 방법을 사용하면 시간복잡도는 O(n²)이다.

 

// main LinkedList<int> L1,L2,L3;
int T3;
 
for (int i = 1; i < 10; i++)
{
    if (i % 2 == 0)
    {
        L1.AddNode(L1.list, L1.CreateNode(i));
    }
    else
    {
        L2.AddNode(L2.list, L2.CreateNode(i));
    }
 
}
std::cout << "\n7-1) ";
L1.PrintAllNode(L1.list);
L2.PrintAllNode(L2.list);
 
 
L3.list = MergeTwoSortedLists(*L1.list, *L2.list); //7-1
L3.PrintAllNode(L3.list);
 
std::cout << "\n7-2) ";
ReverseSublist(*L3.list, 2, 5); //7-2
L3.PrintAllNode(L3.list);
 
T3 = HasCycle(*L1.list)->data;
std::cout << "\n7-3) " << "사이클 시작 지점 : " << T3 << std::endl;
if (HasCycle(*L3.list) == nullptr) { std::cout << "7-3) " << "사이클이 존재하지 않습니다." << std::endl; } // 7-3
 
T3 = HasCycle_2(*L2.list)->data;
std::cout << "\n7-3) " << "사이클 시작 지점 : " << T3 << std::endl;
if (HasCycle_2(*L3.list) == nullptr) { std::cout << "7-3) " << "사이클이 존재하지 않습니다." << std::endl; } // 7-3

문제 7.1 과 7.2 에서 사용한 L1, L2, L3를 다시 사용하여 비교를 진행하였다.

결과