[LeetCode] 141. Linked List Cycle - Java

https://leetcode.com/problems/linked-list-cycle/description/

Linked List Cycle - LeetCode

---

문제

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

---

풀이

풀이 과정

주어진 리스트 안에서 노드의 순환이 존재하는지를 판단하는 문제이다.
플로이드의 토끼와 거북이 알고리즘(Floyd's Tortoise and Hare Algorithm)이라고 하는 순환 탐색 알고리즘을 이용한다.
플로이드의 토끼와 거북이 알고리즘은 빠르게 움직이는 포인터 하나와 느리게 움직이는 포인터 하나를 사용하여 순환이 존재한다면 그 순환 안에서 두 포인터가 반드시 만나게 된다는 개념을 이용한 알고리즘이다.
시계의 시침과 분침을 생각하면 될 듯하다. 1시부터 12시까지 계속해서 시침 분침이 순환하는데 분침이 시침보다 빠르게 이동하여 계속해서 두 포인터가 교차하게 된다.

Linked List에 이 개념을 도입하여 풀이해본다.
먼저 빠르게 이동할 포인터와 느리게 이동할 포인터를 지정한다. 이때 각 포인터는 List의 head부터 시작한다.

ListNode fast = head; // 포인터를 두 칸씩 이동할 리스트
ListNode slow = head; // 포인터를 한 칸씩 이동할 리스트

 

이후 빠르게 이동하는 포인터는 노드를 두 칸씩 이동하고, 느리게 이동하는 포인터는 노드를 한 칸씩 이동하며 반복탐색한다. 두 값이 같아지는 지점이 있다면 순환(Cycle)이 존재한다고 할 수 있다.
만약 빠르게 이동하는 포인터가 먼저 null에 도달하는 경우에는 순환(Cycle)이 존재하지 않는다는 의미이므로 탐색을 종료하고 false를 반환한다.

// fast의 현재 노드나 다음 노드가 먼저 null에 도달하게 된다면
// Cycle이 존재하지 않는 리스트
while(fast != null && fast.next != null){
    // fast의 포인터를 두 칸씩 이동
    fast = fast.next.next;
    // slow의 포인터를 한 칸씩 이동
    slow = slow.next;

    // Cycle이 존재한다면 Cycle안에서 두 포인터가 언젠가는 만나게 됨
    if(fast == slow){
        return true;
    }
}

return false;

---

최종 코드

/**
 * 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 fast = head; // 포인터를 두 칸씩 이동할 리스트
        ListNode slow = head; // 포인터를 한 칸씩 이동할 리스트

        // fast의 현재 노드나 다음 노드가 먼저 null에 도달하게 된다면
        // Cycle이 존재하지 않는 리스트
        while(fast != null && fast.next != null){
            // fast의 포인터를 두 칸씩 이동
            fast = fast.next.next;
            // slow의 포인터를 한 칸씩 이동
            slow = slow.next;

            // Cycle이 존재한다면 Cycle안에서 두 포인터가 언젠가는 만나게 됨
            if(fast == slow){
                return true;
            }
        }

        return false;
    }
}

---