단 사슬 표 에 고리 가 있 는 것 을 판단 하 는 세 가지 방법
1. 노드 ListNode 에 도 메 인 을 추가 하여 이 노드 가 방문 되 었 는 지 기록 합 니 다. 다음 ListNode 에서 코드 가 주석 되 어 있 습 니 다.이 방법 은 간단 해서 링 이 시작 되 는 노드 를 찾 을 수 있 지만 링크 의 비용 을 증가 시 켰 다.링크 가 매우 크 면 이 도 메 인 을 저장 하기 위해 서 는 아주 큰 메모리 가 필요 합 니 다.
2. 링크 역순 을 사용 하 는 방법.처음부터 링크 를 역순 으로 하고 머리 노드 의 next 도 메 인 을 비 웁 니 다.링 이 있 으 면 링크 역 서 는 반드시 머리 노드 로 돌아 가 종 료 됩 니 다.이 방법 역시 O (n) 시간 종료 알고리즘 을 확보 하 는 것 이 간단 하 다.하지만 링크 구 조 를 수정 했다.원 링크 가 바 뀌 었 습 니 다.근 데 링 시작 부분 을 찾 을 수가 없어 요.
3. 두 개의 변 수 를 사용 하여 경 주 를 하고 한 변 수 는 두 걸음 / 번, 한 변 수 는 한 걸음 / 번 걷는다.링 이 있 으 면 두 변 수 는 반드시 만 날 것 이다. 그 중에서 빠 른 변 수 는 느 린 변수 보다 한 바퀴 더 걷는다.이 알고리즘 은 링크 의 고리 가 매우 크 면 비교적 큰 시간 이 필요 합 니 다.이 알고리즘 은 링 이 시작 되 는 곳 도 찾 을 수 있다.
class ListNode {
int val;
ListNode next;
// Boolean visited=false;
ListNode(int x) {
val = x;
next = null;
}
}
방법 1.
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null)
return false;
while(head!=null){
if(head.visited==false)
head.visited=true;
else
return true; // vistited true 。
head=head.next;
}
return false;
}
}
방법 2.
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null)
return false;
ListNode p = head;
ListNode q = head.next;
ListNode k = head.next.next;
while (k != null) {
if (p == k || k == head)
return true;
if (p == head)
p.next = null;
q.next = p;
p = q;
q = k;
k = k.next;
}
return false;
}
}
return false;
ListNode p = head;
ListNode q = head.next;
ListNode k = head.next.next;
while (k != null) {
if (p == k || k == head)
return true;
if (p == head)
p.next = null;
q.next = p;
p = q;
q = k;
k = k.next;
}
return false;
}
}
方法三、
/*找出环开始的节点证明:设链表长度为N(每个节点访问一次) 链表头到达环开始节点长度为 s ,环的大小为S因为 快节点比慢节点多跑一圈 到达相遇节点, 设n为循环的次数。 所以有 2*n-n=S =》 n=S,即到达相遇节点的时候慢节点相当于刚好走了一个环的大小。所以慢节点走完链表N剩下的节点为N-S。而从头节点到环开始的距离s =N-S。所以从头结点开始和慢节点同时再走N-S步即能在环开始的地方相遇。*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode meetNode = fineNode(head);
if (meetNode == null) // ,
return null;
while (meetNode != head) {
head = head.next;
meetNode = meetNode.next;
}
return meetNode;
}
public static ListNode fineNode(ListNode head) {
if (head == null)
return null;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) { // ,
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return slow;
}
}
return null;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
데이터 구조의 링크 의 실현글 목록 소개 실현 1. 프로필 동적 배열, 스 택 과 대열 의 바 텀 은 모두 정적 배열 에 의존 하고 resize 로 고정 용량 문 제 를 해결한다.그리고 링크 는 진정한 동적 데이터 구조 이다 2. 실현...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.