[LeetCode] 141. Linked List Cycle

141. Linked List Cycle

LeetCode

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.

연결 리스트의 헤드(head)가 주어졌을 때, 해당 연결 리스트 내에 사이클(순환)이 존재하는지 판별하세요.
next 포인터를 계속 따라갔을 때 다시 도달할 수 있는 노드가 리스트 내에 존재한다면, 연결 리스트에 사이클이 있는 것입니다. 내부적으로 pos는 리스트의 마지막(tail) 노드의 next 포인터가 연결된 노드의 인덱스를 나타내는 데 사용됩니다. pos는 매개변수로 전달되지 않는다는 점에 유의하세요.
연결 리스트에 사이클이 있다면 true를 반환하고, 그렇지 않다면 false를 반환하세요.

 

Example

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).

 

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.

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

 

---

1. 문제 요구사항 분석

연결 리스트의 사이클 존재 여부 확인하는 문제

2. 접근 전략

😭 Set을 이용하여 동일한 ListNode 주소값이 있는지 확인 

- 시간복잡도 : O(N) / 공간복잡도 : O(N)

import java.util.*;
/**
 * 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) {
        Set<ListNode> set = new HashSet<>();
        while(head != null) {
            if (set.contains(head)) {
                return true;
            }
            set.add(head);
            head = head.next;
        }

        return false;
    }
}

 

😁 토끼와 거북이 알고리즘 (투 포인터)

 

• 거북이는 1초에 1칸씩 이동 (속도: 1)
• 토끼는 1초에 2칸씩 이동 (속도: 2)
• 매번 거리가 정확히 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 slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast) return true;
        }
        return false;
    }
}