문제

• linke list에 cycle이 있으면 true 리턴

풀이

• 어차피 Node.next가 한 노드 밖에 연결하지 못하니까
• dfs로 탐색하며
• visited인 노드를 다시 만나면 true, 아니면 false
  => 문제가 발생했다. val 이 같아도 다른 node가 있는 것..
  => 같은 주소의 노드인지 판별해야한다

from collections import defaultdict

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head:
            visited = defaultdict(list)
            thisNode = head
            visited[thisNode.val].append(thisNode)
            while thisNode.next:
                nextNode = thisNode.next
                if nextNode.val in visited:
                    for visitedValNode in visited[nextNode.val]:
                        if visitedValNode is nextNode:
                            # address compare
                            return True
                visited[nextNode.val].append(nextNode)
                thisNode = nextNode
        return False

예외처리

1. input으로 None인 Node 들어 올 경우
   -> if 처리

결과

너무 느리다 너무 느려
개선이 필요하다

id()를 이용해서 주소값을 비교하기

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head:
            visited = set()
            thisNode = head
            visited.add(id(thisNode))
            while thisNode.next:
                nextNode = thisNode.next
                if id(nextNode) in visited:
                    return True
                visited.add(id(nextNode))
                thisNode = nextNode
        return False

여전히 그닥 빠르진 않다;;;;

set() 대신 dict() 사용하기

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head:
            visited = dict()
            thisNode = head
            visited[id(thisNode)] = True
            while thisNode.next:
                nextNode = thisNode.next
                if id(nextNode) in visited:
                    return True
                visited[id(nextNode)] = True
                thisNode = nextNode
        return False

hash() 사용하기

무조건적으로 dict가 set보다 빠른건 또 아닌가보다...

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head:
            visited = set()
            thisNode = head
            visited.add(hash(thisNode))
            while thisNode.next:
                if hash(thisNode.next) in visited:
                    return True
                thisNode = thisNode.next
                visited.add(hash(thisNode))
        return False

• hash()는 python의 내장함수
• hash 값 리턴함 -> 다른 객채면 다른 hash 갖고, 같은 객체면 같은 hash 갖을 것.