240306 LeetCode 문제 풀이

141. Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/description/?envType=daily-question&envId=2024-03-06

 

1) 문제 설명

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.

 

2) 제한 사항

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

 

3) 도전 과제

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

 

4) 풀이

Set을 만들어서 각 노드의 주소값을 보관한 후, 재귀를 이용해 다시 돌아가는지 아닌지를 판단하였다.

 

다른 사람들의 풀이를 보니 "투 포인터" 문제였다.

 

한번에 두 칸씩 가는 fast 포인터와, 한 칸씩 가는 slow 포인터를 둔다. 두 포인터가 만난다면 사이클이 존재한다. fast 포인터의 다음 지점이 null 일 경우, 사이클이 존재하지 않는다.

 

5) 소스 코드 및 결과

/**
 * 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) {
        HashSet<ListNode> set = new HashSet<>();
        
        if(head == null){
            return false;
        }

        return recursion(head, set);
    }

    public boolean recursion(ListNode head, HashSet<ListNode> set){    
        if(head.next == null){
            return false;
        }

        set.add(head);
        if(set.contains(head.next)){
            return true;
        }

        return recursion(head.next, set);

    }
}

 

6) 다른 사람의 풀이

/**
 * 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; // Initialize fast pointer to head
        ListNode slow = head; // Initialize slow pointer to head
        while (fast != null && fast.next != null) { // Traverse the list until fast pointer reaches end or NULL
            fast = fast.next.next; // Move fast pointer two steps ahead
            slow = slow.next; // Move slow pointer one step ahead
            if (fast == slow) { // If fast meets slow, there is a cycle
                return true;
            }
        }
        return false; // If fast reaches NULL, there is no cycle
    }
}