English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
이 예제에서는 Java에서 LinkedList에서 반복이 있는지 검사하는 방법을 배웁니다.
이 예제를 이해하려면 다음을 알아야 합니다:Java 프로그래밍주제:
class LinkedList { //Node 클래스의 객체 생성 //링크드리스트의 머리를 나타냄 Node head; //정적 내부 클래스 static class Node { int value; //각 노드를 다음 노드에 연결 Node next; Node(int d) { value = d; next = null; } } //루프 존재 여부 확인 public boolean checkLoop() { //LinkedList의 시작 부분에 두 참조 생성 Node first = head; Node second = head; while(first != null && first.next != null) { //첫 번째 참조 이동2개 노드 first = first.next.next; //두 번째 참조 이동1개 노드 second = second.next; //두 참조가 일치하는 경우(만나) if(first == second) { return true; } } return false; } public static void main(String[] args) { //LinkedList 객체 생성 LinkedList linkedList = new LinkedList(); //각 링크드리스트 노드에 값 지정 linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); Node fourth = new Node(4); //링크드리스트의 각 노드를 다음 노드에 연결 linkedList.head.next = second; second.next = third; third.next = fourth; //LinkedList에서 루프 진행 fourth.next = second; //노드 값 출력 System.out.print("LinkedList: "); int i = 1; while (i <= 4) { System.out.print(linkedList.head.value + ""); linkedList.head = linkedList.head.next; i++; } //메서드 호출하여 루프 확인 boolean loop = linkedList.checkLoop(); if(loop) { System.out.println("\nLinkedList에 루프가 있습니다."); } else { System.out.println("\nLinkedList에 루프가 없습니다."); } } }
출력 결과
LinkedList: 1 2 3 4 LinkedList에 루프가 있습니다.
위의 예제에서 Java로 LinkedList를 구현했습니다.사용했습니다.Floyd의 루프 탐색 알고리즘LinkedList에 루프가 있는지 확인합니다.
checkLoop() 메서드 내의 코드에 유의하세요. 여기서 first, second라는 두 개의 변수가 LinkedList의 노드를 탐색합니다.
first - 한 번의 반복에서 사용합니다.2개의 노드를 탐색합니다
second - 한 번의 반복에서 사용합니다.1개의 노드를 탐색합니다.
두 노드를 다른 속도로 탐색합니다. 따라서 LinkedList에 루프가 있으면 그들은 만날 것입니다.