Linked List Loops(Python)

Q4.py

0.05MB

Linked list의 loop이 있는지 확인하는 건

 

1칸 씩 이동하는 slow와 2칸 씩 이동하는 Fast를 선언해서 T/F를 반환할 수 있었다고 알고 있었는데,

 

전체 list의 길이를 반환하는 거는 처음봤다.

 

일차적으로 내가 풀었을 땐

 

# Do not modify!
class LinkedNode:
  def __init__(self, value):
    self.value = value
    self.next = None
    
def hasLoop(head):
    if not head : return 0, True
    if not head.next : return 1,True
    slow = head
    fast = head.next
    cond = False
    while fast and fast.next :
        if slow==fast :
            cond = True
            break
        slow = slow.next
        fast = fast.next.next
    if not cond :
        cnt = 0
        curr = head
        while curr:
            cnt+=1
            curr=curr.next
        return cnt,cond
    else:
        cnt = 0
        lst=[]
        curr = head
        while curr not in lst:
            cnt +=1
            lst.append(curr)
            curr = curr.next
        return cnt,cond

 

이런식으로 풀었는데, 뭔가 list를 또 새로 만들고 하는 게 찝찝했다.

 

그래도 이런식으로라도 방법을 생각해낸 내가 기특하긴 하다 ㅎㅎ.. leetcode로 맞으면서 구른 보람이 있긴 하네

 

GPT를 참고한 답안은 아래와 같다.

 

# GPT 복기
def hasLoop(head):
    if not head : return 0, True
    if not head.next : return 1,True
    slow=head
    fast=head
    cond = False
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            cond = True
            break
    if cond:
        #루프길이
        loop = 1
        fast = fast.next
        while slow != fast:
            loop +=1
            fast=fast.next
        #리스트시작 -> 루프시작점까지의 거리
        start = 0
        slow = head
        while slow != fast:
            start +=1
            slow = slow.next
            fast = fast.next
        ans = loop + start
#         print(loop,start,ans)
    else : # No loop
        slow = head
        ans = 1
        while slow.next :
            ans+=1
            slow = slow.next
    return ans,cond

 

Loop가 있는 경우, list의 시작점에서 Loop시작점까지의 거리를 구하는 것이 좀 이해가 안 갔는데,

 

이 역시도 수학적으로 증명이 가능한 부분이란다.

 

이게 코딩문제야 수학문제야~~

 

루프의 시작점을 찾는 이유 설명 루프의 시작점을 찾기 위해 사용되는 방법은 다음과 같습니다: 루프가 감지되면, slow와 fast 포인터가 루프의 임의의 지점에서 만납니다. 한 포인터(slow)를 리스트의 시작점으로 되돌립니다. 두 포인터를 동일한 속도로 이동시킵니다. 두 포인터가 다시 만나는 지점이 루프의 시작점입니다. 이 방법이 항상 작동하는 이유는 다음과 같습니다: 증명 루프 감지 후 두 포인터의 위치: 두 포인터가 루프 안에서 만났을 때, 이 지점을 M이라고 합니다. 루프의 시작점을 L이라고 합니다. 리스트의 시작점에서 루프의 시작점까지의 거리를 d라고 합니다. 루프의 길이를 C라고 합니다. 포인터의 이동 거리: slow가 리스트의 시작점에서 루프의 시작점까지 이동한 거리: d slow가 루프에서 이동한 거리: x fast가 루프에서 이동한 거리: 2x (왜냐하면 fast는 slow보다 두 배 빠르게 이동) 두 포인터가 만난 지점: 두 포인터가 만난 지점에서 fast가 이동한 총 거리는 d + nC + x이고, n은 루프를 몇 바퀴 돌았는지 나타냅니다. slow가 이동한 총 거리는 d + x입니다. fast는 두 배 빠르게 이동하므로: 2(d + x) = d + nC + x 이 식을 풀면: 2d + 2x = d + nC + x 따라서: d + x = nC 이 식은 d + x가 루프의 길이의 배수임을 나타냅니다. 루프의 시작점을 찾기 위한 포인터 이동: 두 포인터가 만난 후, 한 포인터를 리스트의 시작점으로 이동시킵니다. 두 포인터를 동일한 속도로 이동시킵니다. 첫 번째 포인터가 d 거리를 이동하면, 두 번째 포인터는 이미 루프 안에서 d 거리를 이동하게 됩니다. 두 포인터는 루프의 시작점 L에서 만나게 됩니다.