LeetCode 141. Linked List Cycle
Question
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
첫 번째
Submission
Reference
이 문제에 관하여(LeetCode 141. Linked List Cycle), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://zenn.dev/az/articles/az-leetcode-kotlin-141텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)