1. 연결리스트 길이로 풀기

1
2
3
4
5
6
def isCircleLinkedlist(Linked_list):
    node = Linked_list.head
    for _ in range(len(Linked_list)):
        node = node.next

    return True if node else False
  • 연결리스트의 길이를 구하여 연결리스트의 마지막 노드의 next 를 확인한다.
    • 만약 마지막 노드의 next가 있다면, 순환연결리스트
    • 그렇지 않으면 연결리스트이다.

2. 집합을 사용하여 풀기

1
2
3
4
5
6
7
8
9
10
def isCircleLinkedlist(Linked_list):
	s = set()
	node = Linked_list.head
	while node:
		if node in s:
			return True

		s.add(node)
		node = node.next
	return False
  • 노드의 값이 중복되지 않는다면, 지나간 노드를 집합(set)에 저장한다.
  • 노드가 이동할 때 마다 집합에 있는 노드인지 확인한다.
    • 집합에 지나간 노드가 있으면 True
    • 그렇지 않으면 False

3. 중복된 값이 있을 경우, 두개의 포인트를 사용하여 풀기

1
2
3
4
5
6
7
8
9
def isCircleLinkedlist(Linked_list):
    node1 = node2 = Linked_list.head
    while node1 and node1.next:
        node1 = node1.next.next
        node2 = node2.next

        if node1 == node2:
            return True
    return False
  • node1은 두칸씩 이동한다.
  • node2는 한칸씩 이동한다.
  • 만약 순환이 있다면 언젠가는 두 노드가 만난다.
  • 순환이 없다면 node1 또는 node1.next가 None에 도달한다.