[Linked List] Linked List Cycle

연결리스트 사이클

Linked List Cycle - LeetCode

연결된 목록의 선두인 가 주어 head지면 연결된 목록에 순환이 있는지 확인합니다.

포인터 를 계속 따라가면 다시 도달할 수 있는 노드가 목록에 있는 경우 연결 목록에는 순환이 있습니다  next . 내부적으로 tail의  포인터가 연결된  pos 노드의 인덱스를 나타내는 데 사용됩니다  . 매개   변수로 전달되지 않습니다 .nextpos

true연결리스트에 순환이 있으면 반환합니다  . 그렇지 않으면 를 반환합니다 false.

 

예시 1:

입력: head = [3,2,0,-4], pos = 1
 출력: true
 설명: 연결 목록에 꼬리가 첫 번째 노드(0-인덱스)에 연결되는 순환이 있습니다.

예 2:

입력: head = [1,2], pos = 0
 출력: true
 설명: 연결된 목록에는 꼬리가 0번째 노드에 연결되는 순환이 있습니다.

예시 3:

입력: head = [1], pos = -1
 출력: false
 설명: 연결된 목록에 순환이 없습니다.

 

제약:

• 목록의 노드 수가 범위 내에 있습니다 .[0, 104]
• -10^5 <= Node.val <= 10^5
• pos-1또는 연결된 목록의 유효한 인덱스 입니다 .

---

 

1.첫번째 시도

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
          ListNode rabbit = head;
          ListNode turtle = head;

        while(rabbit != null && rabbit.next != null){
            rabbit = rabbit.next.next;
            turtle = turtle.next;
            if(rabbit == turtle){
                return true;
            }
        }
        return false;
        
    }
}

문제 접근방법

1. 토끼와 거북이를 설화를 생각해보았다. 속도가 빠른 토끼와 속도가 느린 거북이를 같은 지점에서 출발시키면 경기장이 연결되지 않았다면 토끼가 결승점에 먼저 도달할 것이고 경기장이 연결이 되었다면 토끼는 언젠가는 거북이를 추월하는 지점이 생긴다. 이것을 이용하여 경기장이 연결 되어 있는지 끊어져 있는지 확인 하였다.
2. 노드의 head를 head.next.next(rabbit)과 head.next(turtle)로 나누었고 while문으로 반복하였다
3. 만약 head.next.next(빠른)가 null이면 끝에 도달한 것이기 때문에 연결되어있지 않는다고 판단하였다.
4. 만약 rabbit==turtle head가 같다면 rabbit이 turtle을 따라잡은 것으로 판단하여 연결되어 있다고 판단하였다.
5. 이러한 방법을 플로이드의 사이클 검출 알고리즘(Floyd's Cycle Detection Algorithm) 원리 라고 한다.