leetcode : Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/

Linked List Cycle - LeetCode

 

값의 범위가 -30000~30000이라서 처음엔 지나간 노드의 값을 -30001로 바꾸면서 지나가는 방법으로 풀었는데

생각해보니까 리스트 값을 변경하지 말라고 할거같아서 다른 방법을 찾아보다가

두 개의 포인터를 두는 방법을 생각했다.

 

한 포인터는 한 칸씩 앞으로 가고

두 번째 포인터는 두 칸씩 앞으로 간다.

싸이클이 있다면 두 개의 포인터는 언젠가 같은 노드에서 만나게 된다.

 

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        node1 = head
        node2 = head
        
        while node1 and node2:
            node1 = node1.next
            node2 = node2.next
            if node2:
                node2 = node2.next
            if node1 and node1 == node2:
                return True
            
        return False

 

근데 뭔가 썩 맘에 들지 않는다.

 

다른 사람들도 이렇게 풀었구만

class Solution(object):
    def hasCycle(self, head):
        marker1 = head
        marker2 = head
        while marker2!=None and marker2.next!=None:
            marker1 = marker1.next
            marker2 = marker2.next.next
            if marker2==marker1:
                return True
        return False