[Leetcode Week1] [투 포인터] 141. Linked List Cycle

리트코드 문제 세트

리트코드 Week1은 대체적으로 프로그래머스 Lv.1 ~ Lv.2 로 구성되어있어서 평이하였으며, 프로그래머스나 백준 플랫폼과는 조금 달랐던 점이 자료구조 시간에 배웠었던 Linked List, Binary Tree 등의 유형이 많았다는 점이었다.

그런데 141번 Linked List Cycle에서 사이클을 판정하는 문제가 나왔고, 처음 보는 유형이라 어떻게 풀이해야할지 몰라 당황스러웠다.
이미 방문한 노드에 대한 방문 표시를 해주어야 할지?...

검색해보니 투 포인터를 응용해서 푸는 문제라는 힌트를 얻었는데,
내가 접해본 투 포인터는 st 와 en 이 각각 처음과 끝에서 진행해서 서로 교차하는 시나리오 밖에 없어서 더 멘붕이었다.

그래서 공부할 겸~ 자료들을 서치해보니 너무 좋은 자료가 있어서 다음 링크의 포스팅을 많이 참고하여 공부하였다.
[알고리즘] Two pointers 1

투 포인터(Two Pointer) 유형

---

Two-pointer techinque에는 2가지의 시나리오가 존재한다고 한다.

1. starts at different position
2. moved at different speed (slow-pointer and fast-pointer problem)

이 중에 나는 첫번째, 1. starts at different position 밖에 몰랐었다!
이번 기회에 2. moved at different speed 유형을 알아보자.

singly linked list에서는 포인터의 방향이 단방향으로만 진행할 수 있으므로 2번 유형만을 적용할 수 있겠다.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL) return false;

        ListNode *slow = head;
        ListNode *fast = head; // fast = slow*2

        while(fast != NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return true;
        }
        return false;
    }
};