[LeetCode] Linked List Cycle 파이썬 (is operator, id)

2가지 풀이법(1: fast & slow, 2: marked as read)

풀이 1 (fast, slow)

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

class Solution:
    # @param head, a ListNode
    # @return a boolean
    def hasCycle(self, head):
        fast, slow = head, head
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
            if fast is slow:
                return True
        return False

 

어떻게 풀어야 할지 전혀 감이 안왔던 문제

fast, slow라는 2개의 head 의 copy를 받은 다음

fast는 2-step으로 node를 이동하고 slow는 1-step으로 이동한다(next)

 

첫 번째 test case의 경우 이러한 cycle안에서 동작하는데

(괄호 안의 값)은 n번째 움직임을 나타낸 것이다.

3번 이동했을 경우 fast와 slow가 동시에 위치해 있는 곳이 -4 다.

 

같은 노드에 있는 지 여부를 체크하기 위해 "is" operator를 사용한다.

 

is operator: is 연산자는 객체(object)의 id값을 == 연산자로 확인하는 것이다 (출처: link)

 

실제로 print로 확인해보자

fast "is" slow 일 때

fast의 id, slow의 id, fast.val, slow.val이

-4 에서 만나는 것을 알 수 있다.

이때의 id값이 동일하다

(node의 값이 아니라 id 상수로 판단하는 이유는 node의 값이 같지만 다른 id일 경우가 있기 때문에 이렇게 설정한 것이라고 추측)

 

+

----------------------------------------------------------------------

"==" VS. "is" 의 차이점:

- 동등성 Equality "=="

• 피연산자들의 데이터/값(value) 이 같은지를 비교합니다

- 동일성 Identity "is"

• 피연산자들의 주소/고유한 상수(ID) 가 같은지 비교합니다

출처: taejin0527.github.io/[object%20Object]/PY-is-operator/

----------------------------------------------------------------------

 

while 문의 조건은 node가 1개일 경우 cycle이 될 수 없기 때문에

fast and fast.next가 있을 때만(2개 이상의 노드가 있을 경우에만)

순회하면서 체크하는 것이다.

 

 

코드 출처: github.com/jiapengwen/LeetCode/blob/master/Python/linked-list-cycle.py

---

풀이 2 (mark as read)

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        cur = head
        while cur:
            if cur.val == 's':
                return True
            else:
                cur.val = 's' #any character works
                cur = cur.next
        return False

이동한 노드를 "s"로 marked as read 하면서 이미 지난 노드를 다시 방문할 경우 return