LeetCode 141번 Linked List Cycle 문제풀이

문제

(자세한 워딩은 생략)

요약하자면 Singly Linked로 구성된 List에서 tail이 list 어디론가 다시 연결되는 cycle이 발견되는 경우 true를, 순환 없이 끝나면 false를 리턴하라는 문제이다.

그리고 이제부터 답을 향한 대 서사시를 시작해보도록 하겠다😩

는.. 그 전에

풀이

혹시나 답만 필요한 구글러가 있을 지 모르므로 답 코드 먼저 공개하며 시작.

func hasCycle(_ head: ListNode?) -> Bool {
    
    if head == nil { return false }
    
    var slow = head
    var fast = head?.next
    
    while true {
        if fast == nil { return false }
        if slow === fast { return true }
        slow = slow?.next
        fast = fast?.next?.next
    }
    
}

알고 보면 너무나도 간단하다.

다른 속도로 움직이는 두 노드를 설정하고 그 노드가 같은 경우가 생기는 지를 비교하면 된다. 더 빨리 움직인 노드가 nil이라면 사이클이 없는 것이므로 false,

같은 경우가 생긴다면 사이클이 있는 것이므로 true를 리턴하면 끝.

하지만 그 '알고 보면'까지 가는 게 정말 오래 걸렸다😢

지난한 과정들