데이터 구조의 링크 - 링 관련 문제 및 해결 방향 집합

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);
	}

좋은 웹페이지 즐겨찾기