LC 141-Linked List Cycle
문제
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.
예시
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
풀이
- 링크드 리스트의 순환 여부를 검사하는 문제이다.
- 우선
head
가 비어있으면 순환할 노드가 없으므로false
를 반환한다. - 링크드 리스트가 순환한다는 것은 모든 노드의
next
가null
이 될 수 없다는 것과, 맨 끝 노드의next
가 이미 지나온 노드를 가리킨다는 것을 의미한다. - 링크드 리스트 내부를 두 칸 씩 뛰어넘는
runner
와 한 칸 씩 전진하는walker
를 두면, 리스트가 순환 구조라고 했을 때 언젠가는runner
가walker
와 같은 노드에 멈출 때가 온다.
코드
var hasCycle = function(head) {
if (!head) return false;
let walker = head;
let runner = head;
while (runner) {
if (!runner.next) return false;
runner = runner.next.next;
walker = walker.next
if(runner === walker) return true;
}
return false;
};
Author And Source
이 문제에 관하여(LC 141-Linked List Cycle), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@goody/LC-141-Linked-List-Cycle저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)