[LeetCode] Linked List Cycle

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

[

Linked List Cycle - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

](https://leetcode.com/problems/linked-list-cycle/)

리스트에 사이클이 있는지 여부를 판단하는 검사이다. 대기업 코테 준비 당시에는 BFS, DFS만 죽어라 하다가 리스트 관련 문제를 처음 접해서 처음에 풀이법이 잘 떠오르지 않았다.

C#으로 풀었고, 결국은 노드 2개를 이용하는 방식으로 해결했다. 다만 제출 이후에 Submission을 보니 내가 제출한 답보다 간단한 답이 간단하게 있었다..

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
 // C#
public class Solution {
    public bool HasCycle(ListNode head) {
        if(head==null)
            return false;
        ListNode temp = head;
        ListNode temp2 = head.next;
        if(temp2==null)
            return false;
        while(temp2!=null) {
            if(temp2.next==null)
                return false;
            temp2=temp2.next; // 뒤에거 한칸 뒤로
            ListNode cmpTemp = head; //head부터 출발
            do { // temp가 head인 경우
                if(System.Object.ReferenceEquals(cmpTemp,temp2)) // 비교와 뒤 포인터가 같다면 순환
                    return true;
                if(System.Object.ReferenceEquals(cmpTemp,temp))
                    break;
                cmpTemp = cmpTemp.next;
            }while(!System.Object.ReferenceEquals(cmpTemp,temp) || !System.Object.ReferenceEquals(temp,head)); // head부터 앞 포인터까지
            temp=temp.next;
        }
        return false;
    }
}

System.Object.ReferenceEquals는 ==으로 쓸 수 있는데, 중간에 오류가 날 때 객체 비교가 안 되는 것인가 해서 썼었다.
class는 reference type이기 때문에 ==으로 객체 비교가 가능하다.

두 노드를 두고 이동할 때마다 head부터 이전 노드까지 모두 비교하게 하였다. 썩 좋지는 않은 나이브한 방법인 것 같다.