pramp - Move Zeros To End

문제

주어진 배열에서 0을 뒤로 밀어라. (https://www.pramp.com/challenge/9PNnW3nbyZHlovqAvxXW)

input:  arr = [1, 10, 0, 2, 8, 3, 0, 0, 6, 4, 0, 5, 7, 0]
output: [1, 10, 2, 8, 3, 6, 4, 5, 7, 0, 0, 0, 0, 0]

참고로 leetcode move zeros 와 동일한 문제.

해결 brute-force O(n) / O(n)

배열을 추가로 생성하고 기존 배열의 값이 0이아니면 새로 추가. 그런데 공간복잡도가 O(1)인 해결방법을 떠올리려나 머리가 반즘 하얘짐. 솔직히 쉬운 문제인데(심지어 한번 풀어본 문제) 인터뷰 상황에서 생각보다 머리가 굳음.

void moveZerosToEnd(size_t arrLength, const int arr[arrLength], int maxOutSize, int out[maxOutSize])
{
  int outcnt = 0;
  for (int i = 0; i < arrLength; i++) {
    if (arr[i] != 0)
      out[outcnt++] = arr[i];
  }
  for (int i = outcnt; i < maxOutSize; i++) {
    out[i] = 0;
  }
}

다음은 인터뷰 다 끝나고 다시 풀어본것. 참고로 아래부터는 leetcode 에서 풀었다.

해결 O(n) / O(1)

0이 아닌 값을 만나면 기존배열에 앞부터 저장. 그리고 마지막 남은 값은 그냥 0으로 채움. 이렇게하면 추가 배열이 필요없음. (예전에 이렇게 혼자 풀었었는데, 막상 인터뷰 시간에 이게 안떠올랐다! 목 인터뷰를 더 많이 해서 익숙해지는 수밖에 없음)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int retcnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0)
                nums[retcnt++] = nums[i];
        }
        for (int i = retcnt; i < nums.size(); i++)
            nums[i] = 0;
    }
};

해결 two pointer O(n) / O(1)

이 방식은 이번에 처음 풀어봤는데 더 효율적인 풀이 법이다.

기본적으로 0이 아닌 현재 배열값과 마지막 zero를 서로 swap하는것. two pointer는 각각의 포인터를 언제 increase할지를 생각하는 방식으로 접근해야함.

기본적으로 현재배열값은 증가, 0이 아닐때 마지막으로 업데이트된 zero index와 swap한다. 그때 zero index는 +1을 한다. +1만해도 되는 이유는 swap하기 직전 상황이 항상 아래와 같은데, swap을 하면 0의 index는 +1 이 되기 때문.

        nz
1 2 2 0 3 4 
      z

또는

    nz  
1 0 2 0 0 0 0 5
  z
              nz
1 2 0 0 0 0 0 5
    z

class Solution {
    void swap(vector<int>& nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
public:
    void moveZeroes(vector<int>& nums) {
        int retcnt = 0;
        int last_zero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0)
                swap(nums, i, last_zero++);
        }
    }
};

647. Palindromic Substrings

문제

주어진 문자열에서 모든 palindrome(회문)의 substring 갯수를 구하라. substring은 연속된 부분 문자열을 의미.

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

https://leetcode.com/problems/palindromic-substrings/

해결

중앙에서부터 시작해서 palindrome문자인지 판별하는 방법. 이 방법은 문자열이 짝수개, 홀수가 두가지 경우 모두 체크해야한다.

• "abba"
• "aba"

class Solution {
    int ssize;
    
    int palin_center(string &s, int lo, int hi) {
        int cnt = 0;
        
        while (lo >= 0 && hi < ssize) {
            if (s[lo] != s[hi])
                break;
            lo--;
            hi++;
            cnt++;
        }
        return cnt;
    }
public:
    int countSubstrings(string s) {
        ssize = s.length();
        int pcnt = 0;
        
        for (int i = 0; i < ssize; i++) {
            pcnt += palin_center(s, i, i);
            pcnt += palin_center(s, i, i + 1);
        }
        return pcnt;
    }
};

424. Longest Repeating Character Replacement

문제

대문자로 구성된 문자열이 주어지고, 아무 문자로 바꿀수 있는 횟수 k가 주어질때, 동일한 문자로 구성된 substring의 최대 갯수는?

Input: s = "ABAB", k = 2
Output: 4

Input: s = "AABABBA", k = 1
Output: 4

해결 O(n)

생각하기 어려웠던 문제였다. discussion을 좀 참고했음. right와 left를 O(n)동안 하나씩만 이동해도 결과를 얻을수 있는게 직관적으로 와닿지 않음. right를 for문에서 하나씩 증가. 각 루프에서 해당 right까지 내에서 최대 길이 보장됨을 의미. 문자열길이에서 해당 문자열중에 가장 freq가 많은 문자 갯수 를 뺀갯수가 k개를 초과하면 left를 증가시킨다.

속도는 100% 나옴.

#define max(a,b) (((a) > (b)) ? (a) : (b))
int characterReplacement(char * s, int k){
    int freq[26] = {0};
    int maxfreq = 0;
    int ssize = strlen(s);
    int left = 0, right = 0;
    int maxlen = 0;
    
    for (; right < ssize; right++) {
        /* update s[right] freq */
        freq[s[right] - 'A']++;
        maxfreq = max(maxfreq, freq[s[right] - 'A']);
        
        /* if target charactors to change is larger than k */ 
        /* len = right - left + 1 */
        if (right - left + 1 - maxfreq > k) {
            freq[s[left] - 'A']--;
            left++;
        } else {
            maxlen = max(right - left + 1, maxlen);
        }
    }
    return maxlen;
}

4. Median of Two Sorted Arrays

문제

두개의 배열이 주어진다. 전체 배열값중 중간 위치의 값을 리턴하라. (배열이 홀수개면 중간 인덱스값, 짝수개면 두개의 평균값). 단 풀이의 시간복잡도는 O(log(m+n)) 이 되어야한다.

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

해결 O(m+n)

말그대로 두 배열을 정렬된 순서로 합치고 중간값을 계산한 방법. 두 배열을 합치는 two pointer방법은 앞으로 많이 쓸 구조이므로 외워둘것.

O(log(m+n)) 방법이 떠오르지 않아서 일단 O(m+n)으로 푼건데, 답이 맞았음; 그것도 92%로.
Runtime: 14 ms, faster than 92.28%

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int retsize = nums1Size + nums2Size;
    int *ret = (int *)malloc(retsize * sizeof(int));
    int retcnt = 0;
    int i1 = 0, i2 = 0;
    
    while (retcnt < retsize) {
        if (i1 == nums1Size) {
            ret[retcnt++] = nums2[i2++];
            continue;
        }
        if (i2 == nums2Size) {
            ret[retcnt++] = nums1[i1++];
            continue;
        }
        if (nums1[i1] < nums2[i2]) {
            ret[retcnt++] = nums1[i1++];
        } else {
            ret[retcnt++] = nums2[i2++];
        }
    }
    
    int mid = retsize >> 1;
    if (retsize % 2 == 0)
        return (double)(ret[mid - 1] + ret[mid]) / 2;
    else 
        return ret[mid];
}

159. Longest Substring with At Most Two Distinct Characters

문제

문자열이 주어질때, 최대 2개로만 구성된 가장 긴 substring 길이를 리턴하라.

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

아이디어

• two pointer & sliding window (with hashtable)
  • hashtable빈도수가 2개 이하일때 -> right 증가
  • hashtable빈도수가 2개 초과일때 -> left증가
• two pointer 문제는 어떤 조건에서 right를 증가 시킬지, 그리고 어떤 조건에서 left를 증가시킬지를 먼서 생각해보는 전략을 사용하기.

해결 O(n)

O(n) 이지만 빈도수를 체크할때 매번 hashtable 전체를 순회해야해서 비효율적인 방법. (Runtime: 426 ms)

#define TABLE_SIZE 128
#define max(a,b) (((a) > (b)) ? (a) : (b))

int check_nr_char(int *table)
{
    int cnt = 0;
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (table[i] != 0)
            cnt++;
    }
    return cnt;
}

int lengthOfLongestSubstringTwoDistinct(char * s){
    int table[TABLE_SIZE] = {0,};
    int maxlen = 0;
    int ssize = strlen(s);
    int left = 0, right = 0;
   
    table[s[right]]++;
    while (right < ssize) {
        if (check_nr_char(table) <= 2) {
            maxlen = max(maxlen, right - left + 1);
            right++;
            table[s[right]]++;
        }  else {
            table[s[left++]]--;
        }
        
    }
    return maxlen;
}

해결 O(n)

빈도수를 체크할때 hashtable 크기만큼 순회하지 않고, 문자종류 갯수 cur_freq 변수값 하나를 조정해서 수행. 훨씬 효율적이고 빠르다. (Runtime: 22 ms, faster than 80.95%)

hashtable빈도수를 저장할때 0이었다면 총 문자종류개수를 +1 하고, 빈도수를 감소시킬때 0이 된다면 총 문자종류수를 -1 한다.

#define TABLE_SIZE 128
#define max(a,b) (((a) > (b)) ? (a) : (b))

int lengthOfLongestSubstringTwoDistinct(char * s){
    int table[TABLE_SIZE] = {0,};
    int maxlen = 0;
    int ssize = strlen(s);
    int left = 0, right = 0;
    int cur_freq = 1;
   
    table[s[right]]++;
    while (right < ssize) {
        if (cur_freq <= 2) {
            maxlen = max(maxlen, right - left + 1);
            right++;
            if (table[s[right]] == 0)
                cur_freq++;
            table[s[right]]++;
        }  else {
            if (table[s[left]] == 1)
                cur_freq--;
            table[s[left++]]--;
        }
        
    }
    return maxlen;
}

해결 O(n)

위와 동일한 로직인데 아래 코드가 더 논리적으로 이해하기 쉽고 간결. 속도도 더 빠르게 나왔음.
(Runtime: 12 ms, faster than 100.00%)

#define TABLE_SIZE 128
#define max(a,b) (((a) > (b)) ? (a) : (b))

int lengthOfLongestSubstringTwoDistinct(char * s){
    int table[TABLE_SIZE] = {0,};
    int maxlen = 0;
    int ssize = strlen(s);
    int left = 0, right = 0;
    int cur_freq = 0;
   
    while (right < ssize) {
        table[s[right]]++;
        if (table[s[right]] == 1)
            cur_freq++;

        if (cur_freq <= 2) {
            maxlen = max(maxlen, right - left + 1);
        } else {
            table[s[left]]--;
            if (table[s[left]] == 0)
                cur_freq--;
            left++;
        }
        right++;
        
    }
    return maxlen;
}

253. Meeting Rooms II

문제

미팅룸 예약 시간이 담긴 배열이 주어질때, 모든 미팅을 수용할 수 있도록 필요한 최소 미팅룸 갯수를 구하라.[시작시간, 종료시간]

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

https://leetcode.com/problems/meeting-rooms-ii/

해결 O(NlogN)

먼저 시작시간 기준으로 예약을 정렬한다. 그 뒤 다이어그램을 그려보면 순서대로 시작시간을 만나면 방갯수 +1, 종료시간을 만나면 -1을 하고 최대값을 저장해놓으면 그게 해답이 된다.

가령 예약시간이 [[0,30],[5,10],[15,20]] 으로 정렬되어있을때, 시작, 종료를 순차적으로 정렬해서 나열하면 아래와 같다. (괄호)가 시작시간, 아니면 종료시간.

(0) (5) 10 (15) 20 30
 1   2   1   2   1  0

그리고 미팅룸 갯수를 순차적으로 계산하면 최대값이 2가 된다.

여러가지 솔루션으로 해결이 가능해서 코딩테스트 문제로 딱 좋을만한 문제인듯!

#define max(a,b) (((a) > (b)) ? (a) : (b))

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int minMeetingRooms(int** intervals, int intervalsSize, int* intervalsColSize)
{
    int *start = (int *)calloc(intervalsSize, sizeof(int));
    int *finish = (int *)calloc(intervalsSize, sizeof(int));
    for (int i = 0; i < intervalsSize; i++) {
        start[i] = intervals[i][0];
        finish[i] = intervals[i][1];
    }
    qsort(start, intervalsSize, sizeof(int), cmp);   
    qsort(finish, intervalsSize, sizeof(int), cmp);   
    
    int ret = 0;
    int max_room = 0;
    int st_i = 0;
    int fi_i = 0;
    while (st_i < intervalsSize && fi_i < intervalsSize) {
        if (start[st_i] == finish[fi_i]) {
            st_i++;
            fi_i++;
        } else if (st_i < intervalsSize && (start[st_i] < finish[fi_i] || fi_i == intervalsSize)) {
            ret++;
            st_i++;
            max_room = max(ret, max_room);
        } else if (fi_i < intervalsSize && (finish[fi_i] < start[st_i] || st_i == intervalsSize)) {
            ret--;
            fi_i++;
            max_room = max(ret, max_room);
        }
    }
    return max_room;
}

34. Find First and Last Position of Element in Sorted Array

문제

중복된 값이 있는 정렬된 배열이 있을때, target값이 존재하는 범위를 리턴하라. 없다면 [-1,-1]을 리턴.
단, 시간복잡도는 O(log N)을 초과할 수 없다.

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

먼저 축하할 일

Leetcode 에서 200번째로 해결한 문제이다. 딱 두달전 5/9에 100개를 돌파했는데, 속도가 붙어서 어느덧 오늘 7/9이다. 두 달동안 100문제를 풀었다. 대견한 나를 칭찬해주기!

해결 O(logN)

우선 binary search로 target값의 idx하나를 구한뒤, 그 idx로부터 좌/우로 동일한 값을 확장하며 범위를 구하는 방법. 평균적으로 O(logN) 이겠지만 최악의 경우 O(N)이 된다(모든 값이 동일한 경우).
순수하게 O(logN)으로만 해결할 수 있는 방법이 있을까?

int binary_search(int *nums, int left, int right, int target) 
{
    int mid = 0;
    while (left <= right) {
        mid = (left + right) / 2;
        if (target == nums[mid])
            return mid;
        else if (target < nums[mid])
            right = mid - 1;
        else if (nums[mid] < target)
            left = mid + 1;
    }
    return -1;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int *ret = (int *)malloc(sizeof(int) * 2);
    *returnSize = 2;
    int t_idx = 0;
    int l_idx = 0, r_idx = 0;
    
    t_idx = binary_search(nums, 0, numsSize -1, target);
    l_idx = t_idx;
    r_idx = t_idx;
    if (t_idx != -1) {
        while (l_idx - 1 >= 0 && nums[l_idx - 1] == nums[t_idx])
            l_idx--;
        while (r_idx + 1 <= numsSize -1 && nums[r_idx + 1] == nums[t_idx])
            r_idx++;
    }
    ret[0] = l_idx;
    ret[1] = r_idx;
    return ret;
}

two pointer 논리적 구조 구현 방안

220725에 다시 풀어본 방식. binary search로 index를 찾은뒤 중간에서 좌우로 이동하며 같은값이 있는지 찾기. 항상 배열에서 two pointer 를 찾는 것을 어려워함. 두가지 경우로 방법을 정리해보자면

1. 반복문 하나에서 처리할때, 코딩전에 먼저 생각해야할 3가지 조건
   • pointer 1이 어떤 조건에서 증/감 할지
   • pointer 2가 어떤 조건에서 증/감 해야할지
   • 반복문을 언제 탈출해야하는지
2. pointer 각각 반복문을 하나씩 처리하기 (루프 탈출 조건과 증/감 조건이 같은경우)
   이번 문제에서 풀었던 방법. 이번경우는 반복문 하나에서 처리하기에 너무 조건처리가 많아져 머리가 아팠다. 그럴땐 그냥 루프를 각각 생성하는게 편리. 앞으로 이렇게 하는게 좋겠다. 이전에 해결했던 코드보다 읽기에 더 간결함.

    while (l_idx >= 0 && nums[l_idx] == target)
        l_idx--;
    while (r_idx < numsSize && nums[r_idx] == target)
        r_idx++;

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    *returnSize = 2;
    int *ret = (int *)malloc(sizeof(int) * 2);
    
    int idx = binary_search(nums, 0, numsSize - 1, target);
    if (idx == -1) {
        ret[0] = -1;
        ret[1] = -1;
        return ret;
    }
    int l_idx = idx, r_idx = idx;
    while (l_idx >= 0 && nums[l_idx] == target)
        l_idx--;
    while (r_idx < numsSize && nums[r_idx] == target)
        r_idx++;
    
    ret[0] = l_idx + 1;
    ret[1] = r_idx - 1;
    return ret;
}

3. Longest Substring Without Repeating Characters

문제

문자열이 주어질때, 반복된 문자가 없는 가장 긴 substring의 길이를 구하라.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

해결 O(N)

sliding window 로 해결. (discussion참고)

• left/right 두개의 포인터를 이동하면서 window의 사이즈를 변경하여 체크.
• 해시테이블에 빈도수를 저장.
• table[s[right]] 이 2 이상 이라면, 1이하로 줄때까지 left를 증가
  • right가 증가하면서 중복된 값을 만났다는뜻.
• update max lenth

1. constraint
 - 0 <= s.length <= 50000
 - s can be all kind of letter
2. Ideas
 - greedy way O(N) -> X
   - using hashtable to check repeated letter exist
 - brute force with Window size -> O(N^2)  
 - sliding window with two pointer (l, r)
   - increase l, while (table[s[r]] > 1)
3. TC

#define TABLE_SIZE 128

int lengthOfLongestSubstring(char * s) {
    int table[TABLE_SIZE] = {0,};
    int ssize = strlen(s);
    int max_len = 0;
    int left = 0, right = 0;
    
    while (right < ssize) {
        table[s[right]]++;
        while (table[s[right]] > 1) {
            table[s[left]]--;
            left++;
        }
        if ((right - left + 1) > max_len)
            max_len = right - left + 1;
        right++;
    }
    return max_len;
}

추가로 배열에서 두개의 인덱스값 a, b 가 주어졌을때 (a<b)라면 a에서 b의 길이는 b - a + 1이다. 당연한거긴 하지만 매번 만날때마다 계산을 하게되서 뇌를 쓰게된다. 그냥 이 패턴을 외우는게 좋겠다. 코딩시 STM을 최소로 사용. 인지적 부하를 최대한 줄이기.
비슷한 내용을 사용한풀이 :
https://velog.io/@soopsaram/Leetcode-5.-Longest-Palindromic-Substring

11. Container With Most Water

문제

수조와 칸막이가 주어지고 두개를 선택한다고할때 가장 많은 물을 담을 수 있는 경우, 얼만큼의 양을 담을 수 있는가? 가령 아래의 경우, 최대인경우 높이 7 너비 7로 49만큼의 양을 담을 수 있다.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

between height[1] ~ height[7] -> 7 * 7 = 49

해결 O(N^2) -> TLE

당연히 가장 먼저 생각해볼수 있는 쉬운 솔루션은 brute force 방식으로 두개의 막대기를 선택하는 모든 경우의 수를 완전탐색하는것이다. 역시 Time Limited Exeeded발생.

int maxArea(int* height, int heightSize){
    int max_amount = 0;
    int cur_amount = 0;
    
    for (int i = 0; i < heightSize; i++) {
        for (int j = i + 1; j < heightSize; j++) {
            cur_amount = (j - i) * (height[i] < height[j]? height[i]: height[j]);
            if (cur_amount > max_amount)
                max_amount = cur_amount;
        }
    }
    return max_amount;
}

해결 O(N)

left/right 의 two pointer를 어떤조건일때 늘리고 줄여야되는지, 아이디어를 깨닫기 쉽지 않아 discussion을 조금 참고했다.

방법은 매번 반복문마다, left와 right 둘중 작은값을 미리 저장하고, left와 right 둘중에 작은 값의 인덱스를 바로 다음큰값의 인덱스로 이동시키는것. 매번 반복마다 max값을 갱신해서 최종 갱신된 max값을 리턴하면 된다.

#define max(a,b) (((a) > (b)) ? (a): (b))

int maxArea(int* height, int heightSize){
    int max_amount = 0;
    int left = 0;
    int right = heightSize - 1;
    int cur_min_h = 0;
    
    while (left < right) {
        cur_min_h = height[left] < height[right] ? height[left]: height[right];
        max_amount = max(max_amount, (right - left) * cur_min_h);
        /* move the smaller point (between L and R) to the next larger bar */
        while (height[left] <= cur_min_h && left < right) left++;
        while (height[right] <= cur_min_h && left < right) right--;
    }
    return max_amount;
}

392. Is Subsequence

문제

첫번째 문자열이 두번째 문자열의 subsequence인지 판단하기

Input: s = "abc", t = "ahbgdc"
Output: true

https://leetcode.com/problems/is-subsequence/

해결 O(t)

06/07

bool isSubsequence(char *s, char *t){
    int tsize = strlen(t);
    if (*s == '\0' && *t == '\0')
        return true;
    for (int i = 0; i < tsize; i++) {
        if (*s == t[i])
            *s++;
        if (*s == '\0')
            return true;
    }
    return false;
}

07/25 다시 풀었는데 잘 못풀었음.

해결 O(t)

Two Pointer로 해결. 투포인터는 어떤 조건에서 left 와 right 포인터를 증가시킬지 조건을 먼저 따져보는게 우선. 위의 코드보다 이 코드가 더 간결함.

• s_idx 증가 하는 조건
  s[s_idx] == t[t_idx] 일 경우
• t_idx 증가 하는 조건
  기본적으로 t를 순회하므로 루프에서 항상 증가

bool isSubsequence(char *s, char *t) {
    int s_size = strlen(s);
    int t_size = strlen(t);
    int s_idx = 0, t_idx = 0;
    
    while (s_idx < s_size && t_idx < t_size) {
        if (s[s_idx] == t[t_idx])
            s_idx++;
        t_idx++;
    }
    if (s_idx == s_size)
        return true;
    return false;
}

리턴하는 부분을 이렇게 수정해도됨.

    return s_idx == s_size;

141. Linked List Cycle

문제

배열이 주어지고 각 링크드리스트 노드를 나타낸다. pos는 마지막 노드의 next 포인터 위치를 나타낸다. -1 이면 next 포인터는 NULL이다. 이 링크드리스트가 사이클을 갖는지 아닌지 판단하라.

Input: head = [3,2,0,-4], pos = 1
Output: true

해결 O(n) / O(n)

굉장히 흥미로운 문제였다. 노드를 순회하면서 노드의 포인터값을 해시테이블의 key로해서 빈도를 저장했다.
답은 맞았는데, 솔직히 이렇게 해도 되는건지 모르겠다... 포인터주소의 hash collision처리도 안되어있고.. 다음에 다른 방법으로 한번 더 풀어봐야할듯!

1. Constraints
 - single node can be cycle?
 - how many node? 0 ~ 10000
 - the valses can be duplicated? 
 - if pos == -1, what is tail->next? NULL?
2. Ideas
3. TestCases

#define HSIZE 200001
bool hasCycle(struct ListNode *head) {
    struct ListNode *node = head;
    struct ListNode *table[HSIZE] = {0};
    memset(table, 0, sizeof(struct ListNode *) * HSIZE);
    
    for (;node != NULL; node = node->next) {
        if (table[(int)node % HSIZE])
            return true;
        table[(int)node % HSIZE]++;
    }
    return false;
}

해결 O(n) / O(1)

추가 메모리를 사용하지 않고 공간복잡도를 O(1)푸는 방법.
서로 속도가 다른 two pointer기법이다. 한칸씩 이동하는 slow와 두칸씩 이동하는 fast포인터로 루프를 돌리다보면 사이클이 있을때, 이 둘은 언젠가는 만난다. 아주 신박한 방법! (참고로 풀이가 링크드 리스트의 중간노드 찾는것과 동일하다. 루프 종료후 slow가 중간노드)

bool hasCycle(struct ListNode *head) {
    if (head == NULL)
        return false;
    struct ListNode *slow = head, *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        if (slow == fast)
            return true;
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}