<Easy> Linked List Cycle (LeetCode : C#)

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

📕 문제 설명

연결 리스트의 head가 주어질 때 cycle이 있는지 없는지 반환

cycle: 노드가 재 방문 되는 경우

• Input
  연결 리스트의 head (ListNode)
• Output
  주어진 연결 리스트에서 cycle의 존재 여부 (bool)

예제

풀이 1.

set으로 현재 들어오는 노드들 저장해두고, 만약 포함한다면 cycle이 있는 것이니 true, 아니면 false 반환

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public bool HasCycle(ListNode head) {
        if (head == null) return false;
        
        HashSet<ListNode> set = new HashSet<ListNode>();
        ListNode currNode = head;
        set.Add(currNode);

        while (currNode != null)
        {
            currNode = currNode.next;
            if (set.Contains(currNode))
            {
                return true;
            }
            set.Add(currNode);
        }

        return false;
    }
}

결과 1.

풀이 2.

1) 한 칸씩 움직이는 slow 노드랑 2 칸씩 움직이는 fast 노드를 둔다.
2) 빨리 가는 노드가 끝나는 지점을 보면 cycle 없으므로 false
3) fast가 빨리 돌기 때문에 cycle 있으면 결국 slow를 따라잡게 된다. 따라 잡게 되면 return true

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public bool HasCycle(ListNode head) {
        if (head == null) return false;

        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) 
        {
            if (fast == null || fast.next == null) 
            {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

결과 2.