141. Linked List Cycle(javascript)
Follow up: Can you solve it without using extra space? 별도의 공간 없 이 답 을 내 는 게 좋 을 것 같 아 요.
해:
순환 링크 의 특징 은 표 의 마지막 노드 의 지침 역 이 머리 노드 를 가리 키 고 전체 링크 는 하나의 링 을 형성 하 는 것 이다.왜 빠 르 고 느 린 지침 이 만 나 는 지 이해 가 되 지 않 았 다. 풍 욱 요 를 아 는 대답 을 보면 다음 과 같다.
이 문 제 는 네가 수학 귀납법 으로 생각 할 수 있다.우선, 체인 시계 가 고리 이기 때문에 만 나 는 과정 은 빠 른 지침 이 뒤에서 느 린 지침 을 쫓 는 과정 으로 볼 수 있다.그러면 다음 과 같이 생각 합 니 다.
빠 른 지침 과 느 린 지침 사이 에 한 걸음 차이 가 난다.이때 계속 뒤로 가 고 느 린 지침 앞 에 한 걸음 더 나 아가 빠 른 지침 으로 두 걸음 전진 하 며 둘 이 만난다
빠 른 지침 과 느 린 지침 사이 의 차 이 는 두 걸음 이다.이때 탄식 하 며 뒤로 가 고 느 린 지침 앞 에 한 걸음 더 나 아가 빠 른 지침 으로 두 걸음 전진 하 며 둘 사이 에 한 걸음 차이 가 나 서 첫 번 째 상황 으로 바 뀌 었 다
빠 른 지침 과 느 린 지침 사이 의 차 이 는 N 보 이다.이때 계속 뒤로 가면 느 린 지침 앞 에 한 걸음 더 나 아가 고 빠 른 지침 으로 두 걸음 전진 하 며 둘 사이 의 차이 (N + 1 - 2) - > N - 1 걸음 입 니 다.그래서 이 문 제 는 증 거 를 얻 었 다.그래서 빠 른 지침 은 반드시 느 린 지침 과 만난다.또 빠 른 지침 속도 가 느 린 지침 의 두 배 이기 때문에 만 났 을 때 한 바퀴 만 돌 수 밖 에 없다
자신 이 이해 할 수 있 는 예 를 생각 했다. 만약 에 환상 활주로 가 있다 면 A 와 B 는 달리 고 A 는 1 분 에 한 바퀴 를 뛰 고 B 는 2 분 에 한 바퀴 를 뛰 면 A 와 B 는 두 번 째 바퀴 를 뛸 때 만난다.직선 코스 라면 A 와 B 는 만 날 수 없다.
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
var slow = head, fast = head;
while(true){
if(fast === null || fast.next === null){
return false;
}
slow = slow.next;
fast = fast.next.next;
if(slow === fast){
return true;
}
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
