Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 연결 리스트 사이클(순환) 감지하기

연결 리스트가 주어졌을 때, 이 리스트 안에 사이클(순환)이 존재하는지 판별하는 문제를 생각해 봅시다. 사이클은 리스트의 마지막 노드(tail)가 다시 앞쪽 노드를 가리킬 때 발생합니다.

이 문제에서는 pos라는 정수 포인터를 사용해 사이클을 표현합니다. pos는 꼬리 노드가 연결되는 위치(인덱스)를 의미하며, pos가 -1이면 사이클이 없다는 뜻입니다.

예를 들어 연결 리스트가 [5, 3, 2, 0, -4, 7]이고 pos = 1이라면, 마지막 노드가 두 번째 노드(값 3)에 연결되어 있으므로 사이클이 존재합니다.

해결 접근 방법

가장 간단하고 직관적인 방법은 해시 셋(Set)을 활용하는 것입니다. 노드를 순회하면서 이미 방문한 노드를 기록하고, 같은 노드를 두 번 만나면 사이클이 있다고 판단합니다.

  • 방문한 노드를 저장할 해시 셋 H를 하나 생성합니다.
  • head가 null이 아닌 동안 반복합니다.
    • 현재 head가 이미 H에 존재하면 True(사이클 있음)를 반환합니다.
    • 그렇지 않으면 head를 H에 추가합니다.
    • head를 다음 노드(head.next)로 이동합니다.
  • 반복문이 끝날 때까지 중복 노드를 만나지 못했다면 False(사이클 없음)를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 최악의 경우 O(n)입니다.

구현 예시

아래 코드는 위 접근 방식을 파이썬으로 구현한 것입니다.

class ListNode:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def get_node(head, pos):
    if pos != -1:
        p = 0
        ptr = head
        while p < pos:
            ptr = ptr.next
            p += 1
        return ptr

class Solution(object):
    def hasCycle(self, head):
        hashS = set()
        while head:
            if head in hashS:
                return True
            hashS.add(head)
            head = head.next
        return False

head = make_list([5,3,2,0,-4,7])
last_node = get_node(head, 5)
pos = 1
last_node.next = get_node(head, pos)
ob1 = Solution()
print(ob1.hasCycle(head))

입력

List = [5,3,2,0,-4,7]
Pos = 1

출력

True

동작 원리 정리

위 예제에서 마지막 노드(값 7)는 get_node(head, 1)을 통해 값 3인 두 번째 노드와 연결됩니다. 따라서 hasCycle 메서드가 리스트를 순회하다가 값 3인 노드를 두 번째로 만나는 순간 해시 셋에서 중복을 발견하고 True를 반환하게 됩니다. 만약 pos가 -1이라면 모든 노드를 한 번씩만 지나고 순회가 종료되어 False가 반환됩니다.