[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^4].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

Solution

Logic

1. 헤드 노드에서 시작하여 연결 리스트를 탐색한다. 탐색 중에 지나왔던 모든 노드를 자료 구조에 저장한다.

2. 특정 노드를 참조하고 있을 때, 해당 노드가 자료 구조에 존재한다면 Cycle이 존재한다는 의미이다. 그렇지 않으면 Cycle이 존재하지 않는다는 의미가 된다.

   Code

   /**
    * 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) {
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            if (list.contains(head)) return true;
            list.add(head);
            head = head.next;
        } return false;
    }
   }
   

   Time Complexity

   • 연결 리스트의 길이를 n이라 가정할 때, 코드의 수행 시간을 좌우하는 것은 while반복문의 최소 1 ~ 최대 n번의 계산 횟수이다. 따라서 본 솔루션은 최악 O(1), 최선 O(n)의 시간 복잡도를 가진다.