데이터 구조의 링크 - 링 관련 문제 및 해결 방향 집합
2025 단어 데이터 구조
1. 자신의 링크 구 조 를 구축한다.
class node {
int data;
node next;
public node(int data) {
this.data = data;
}
}
둘째.
링크 에 링 이 있 는 지 판단
사고: 두 개의 지침 을 설정 하고 하 나 는 빠 르 고 하 나 는 느리다 (현재 시장 에서 모두 이런 해법 인 것 같다). 만약 에 빠 른 지침 이 느 린 지침 과 겹 칠 수 있다 면 링크 에 고리 가 존재 한 다 는 것 을 의미한다.코드 는 다음 과 같 습 니 다:
public static boolean IsLoop(node head) {
node p = head;
node q = head.next;
while(p != q && q != null) {
p = p.next;
q = q.next.next;
}
if(p == q) {
return true;
}
else {
return false;
}
}
셋.
고리 길이
사고방식: 속도 포인터 의 첫 번 째 만 남 과 두 번 째 만 남 사이 의 순환 횟수, 즉 링 의 길 이 를 계산한다.
public static int LoopLength(node head) { //
node p = head;//
node q = head.next;//
int flag = 0;
int res = 0;
while(q != null) {
if(p == q) { // flag 1
flag++;
}
if(flag == 1) {
res ++;
}
if(flag == 2) { // break
break;
}
p = p.next;
q = q.next.next;
}
return res;
}
넷.
링 의 출발점 찾기
사고방식: hashtable 로
public static node LoopStart(node head) {
Hashtable table = new Hashtable();
while(head != null) {
if(table.containsKey(head)) {
break;
}
else {
table.put(head, 1);
}
head = head.next;
}
return head;
}
테스트
public static void main(String[] args) {
node n1 = new node(1);
node n2 = new node(2);
node n3 = new node(3);
node n4 = new node(4);
node n5 = new node(5);
n1.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;n5.next = n2;
//1、
System.out.println(IsLoop(n1));
//2、
System.out.println(LoopLength(n1));
//3、
System.out.println(LoopStart(n1).data);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.