[LeetCode] 141. Linked List Cycle - Java

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?

LinkedList가 순환하는지 확인하는 문제이다.

 

---

 

풀이

도저히 어떻게 풀어야할 지 모르겠어서 힌트를 참고했다.

Floyd's Cycle-Finding Algorithm 로 불리는 알고리즘이다.

주어진 연결 리스트를 두 개의 포인터인 slow와 fast를 사용하여 순환 여부를 검사하는 로직으로 구성된다.

 

• slow : 노드를 한 번씩 이동하는 포인터
• fast : 노드를 두 번씩 이동하는 포인터

 

/**
 * 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) {

        if (head == null) return false;

        ListNode current = head;
        ListNode slow = current;
        ListNode fast = current.next;

         while (fast != null && fast.next != null) {
            if (slow == fast) return true;
            slow = slow.next;
            fast = fast.next.next;
        }

        return false;
    }
}

 

1. 만약 head가 null이라면 순환할 노드가 없으므로 false를 반환한다.
2. current, slow, fast 세 개의 포인터를 초기화한다.
   1. current는 현재 노드를 가리키고, slow와 fast는 처음에 모두 current를 가리킨다.
3. slow와 fast 포인터가 서로 다른 노드를 가리키면서 반복문을 실행한다.
   1. fast 포인터는 노드를 두 번씩 이동하므로, 순환이 없으면 fast가 끝에 도달하게 된다.
4. 반복문 내부에서 slow와 fast 포인터가 같은 노드를 가리키면, 이는 순환을 의미하므로 true를 반환한다.
5. 반복문이 종료되면 순환이 없으므로 false를 반환한다.

 

즉, 순환사이클이 존재할 경우 순환이 처음 발생하는 노드를 fast 가 먼저 지나가고 slow는 그 안에서 계속 돌 것이다.

slow와 fast는 한번에 진행하는 차이가 1칸씩 나니까 사이클이 존재한다면 언젠가는 만나게 된다.

 

• 시간복잡도 : O(n) - 최악의 경우 fast 포인터가 순환을 도는 경우까지 최대 n번의 노드 이동이 필요함
• 공간복잡도 : O(1) - 추가적인 공간을 사용하고 있지 않음

 

처음에 링크드 리스트 자체를 이해하는데 시간이 좀 걸려서 여러 풀이와 영상을 찾아보았다.

아래 영상에서 실제 코드가 어떻게 작동하는지 보면서 이해할 수 있었다.