[leetcode #141] Linked List Cycle

Problem

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, 10⁴].
・ -10⁵ <= Node.val <= 10⁵
・ pos is -1 or a valid index in the linked-list.

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

Idea

주어진 List에 Cycle이 존재하는지 확인하는 문제다.

List를 탐색하면서 Node를 set에 저장하고 해당 Node가 set에 존재하면 cycle이 있는 것으로 판별할 수 있다.

하지만 이 때 Space Complexity는 O(n)이 되므로 Space Complexity가 O(1)인 방법을 사용하는 것이 좋다.

List를 탐색할 때 두 개의 포인터를 사용한다. 하나는 Node 하나씩 건너뛰는 포인터, 다른 하나는 Node 두 개씩 건너뛰는 포인터다.

List가 두 개 이하의 노드로 구성되어 있고 끝이 null을 가리킨다면 cycle이 없다고 판단하고 곧바로 false를 리턴한다.

이후 포인터를 옮겨가면서 cycle이 존재하는지 확인한다. 두 개의 포인터가 일치하는 경우, cycle이 있으므로 true를 리턴한다. 포인터를 한 개 또는 두 개의 노드씩 건너뛰게 만드는데, 두 개씩 건너뛰는 포인터는 NullPointerException이 발생할 수 있으므로 이를 추가로 확인한다.

Loop를 빠져나올 경우 cycle이 존재하지 않으므로 false를 리턴한다.

Time Complexity: O(n)
Space Complexity: O(1)

Solution

/**
 * 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 || head.next == null || head.next.next == null) {
            return false;
        }

        ListNode singleJump = head.next;
        ListNode doubleJump = head.next.next;

        while (singleJump != null && doubleJump != null) {
            if (singleJump == doubleJump) {
                return true;
            }

            singleJump = singleJump.next;
            if (doubleJump.next != null) {
                doubleJump = doubleJump.next.next;
            } else {
                doubleJump = null;
            }
        }

        return false;
    }
}

Reference

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