연결 리스트가 있다고 가정하고 순환이 있는지 없는지 확인해야 합니다. 주어진 연결 목록에서 주기를 나타내기 위해 pos라는 정수 포인터 하나를 사용합니다. 이 위치는 연결 리스트에서 꼬리가 연결된 위치를 나타냅니다. 따라서 pos가 -1이면 연결 목록에 사이클이 없습니다. 예를 들어 연결 리스트는 [5, 3, 2, 0, -4, 7], pos =1과 같으므로 주기가 있고 두 번째 노드에 꼬리가 연결됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 한 세트를 해시 세트 H로 사용
- head가 null이 아닌 동안 -
- head가 H에 있으면 true를 반환합니다.
- H에 머리 추가
- head :=머리 옆
- 거짓을 반환
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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