LeetCode 141. Linked List Cycle

Question

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

4

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

매번 익숙한 리스트 노드의 연결 목록 헤드를 제시하기 때문에 사이클의 문제가 있는지 판단한다.Cycle이 링크 목록에 포함되어 있으면 진짜를 반환하고 그렇지 않으면 가짜를 반환합니다.
Cycle 상태가 링크 목록에 있는 것은 목록에 다음 노드를 가리키는 포인터를 계속 추적하여 다시 도달할 수 있는 노드가 있는 경우입니다.
내부적으로pos는 끝에 있는 다음 바늘에 연결된 노드의 인덱스입니다.
pos는 매개 변수로 전달되는 것이 아닙니다.(단순한 사이클의 연결 목록은 헤드와pos로 표현)

Code

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */

class Solution {
    fun hasCycle(head: ListNode?): Boolean {
        var current = head
        val visited = mutableListOf<ListNode>()
        while (current != null) {
            visited.add(current)
            if (current?.next in visited) return true
            current = current?.next
        }
        return false
    }
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */

class Solution {
    fun hasCycle(head: ListNode?): Boolean {
        var normal = head
        var faster = normal?.next

        while (normal != null) {
            if (normal == faster) return true
            normal = normal?.next
            faster = faster?.next?.next
        }
        return false
    }
}

방문이 끝난 ListNode를 목록visited에 넣고 다음 ListNode가visited에 가입했는지 매번 조사합니다
있다면 Cycle이 존재하기 때문에 정말로 끝으로 돌아갑니다.
Cycle이 존재하지 않을 때는 넥스트가 null인 곳에 도착해야 하기 때문에 while를 통해 자연스럽게 휴가로 돌아간다.
애초 리스트노드를 키로 하는 해산 목록(Map)으로 O(n)에서 검색할 수 있는 visited를 관리하는 방식을 시도했지만, 실제 리스트의 프로필이 우수해 리스트에서 FA가 이뤄졌다.
또 다른 해답으로 연결 목록을 따르는 두 개의 바늘을 준비해 다른 속도로 운행해 보자.
링크 리스트가 사이클이라면 빠른 일주일에 느린 쪽을 쫓는 성질을 이용해 문제를 풀 수도 있다.
성능 개선을 보지 못했다.

Profile

첫 번째

Runtime: 320 ms

Memory Usage: 36.9 MB

두 번째

Runtime: 298 ms

Memory Usage: 41.6 MB

Submission

https://leetcode.com/submissions/detail/614295751/

https://leetcode.com/submissions/detail/614312023/