.leetcode(141. Linked List Cycle)

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

 

3. 2022/04/29 시도

소요시간: 12분

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

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

풀이 접근 과정

edge케이스 설정한다.

slow와 fast 속도를 다르게 설정한다.
fast가 끝나면 cycle이 없어 false를 리턴한다.

while문 중에 fast == slow 케이스가 발생하면 cycle이 있으므로 true를 리턴한다.

 

느낀점

• 이런 토끼와 거북이식 링크드리스트 해법 코드를 작성할 때, 초기 세팅값이 늘 궁금했다.
• slow=head, fast=head.next, slow=head, fast=head로 해야하는지 말이다. 그런데 이번에 확실하게 이유를 알았다. 출발은 무조건 같은데서 하되, 비교구문에서 먼저 비교하지말고 먼저 이동시키고 비교하면 된다.
• 혹시나 slow=head, fast=heas.next로 하고 비교를 먼저 하고 싶을 수도 있는데 이는 분명 다른 분제에서 낭패를 당할 것이다.

---

 

 

2. 2022.01.23 시도

소요시간: 7분(5분 구상, 2분 풀이), 1분(hashSet)

// floyd
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        boolean isCycle = false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            if (fast == slow) {
                isCycle = true;
                break;
            }
            
            slow = slow.next;
            fast = fast.next.next;
        }

        return isCycle;
    }
}

풀이 접근 과정

pos=1이게 뭔지 문제보면서 고민했는데 문제와는 관련없었다.

cycle인 경우, slow, fast로 하면 언젠가는 만날 수 있겠다고 생각이 들었다.
아닌 경우는 어차피 돌다가 먼저 끝날테니 false리턴해서 종료하면 된다고 생각했다.

 

느낀점

• 이번에는 저번과 다르게 hashSet은 생각하지 못했다. cycle검사할 때, floyd, hashSet 두개를 기억해두면 좋겠다.

// hashSet
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        
        while(head != null) {
            if (set.contains(head)) {
                return true;
            }
            set.add(head);
            head = head.next;
        }
        
        return false;
    }
}

• 내가 floyd를 기억하고 있다는 것만으로도 뿌듯했다.

 

---

1. 2021.01.10 시도

소요시간: 3분(hashSet), 16분(floyd)

#hashset
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();


        while(head != null) {
            if (set.contains(head.next)) {
                return true;
            }
            set.add(head);
            head = head.next;
        }

        return false;
    }
}

#O(1)
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode lastNode = head;
        while(lastNode != null) {

            if (lastNode.val == Integer.MAX_VALUE) {
                break;
            }
            lastNode.val = Integer.MAX_VALUE;
            lastNode = lastNode.next;
        }

        while(head != null) {
            if (head == lastNode) {
                return true;
            }

            if (head.val == Integer.MIN_VALUE) {
                return false;
            }

            head.val = Integer.MIN_VALUE;
            head = head.next;
        }

        return false;
    }
}

풀이 접근 과정

반복찾는건 hashSet을 쓰면 금방하더라는 생각이 들었다.
좀 치사?한 방법이지만 하지만 val를 이용해서 노드가 재연결되는 부분을 찾앗다.

 

느낀점

• 반복 문제를 풀때는 꼭 hashSet을 염두해보자.
• 역시 val을 이용한건 문제에서 원하는 정답은 아니었다.
• 진짜 공간을 1만 사용하는 방법은 소위 "플로이드의 거북이와 토끼" 방법이다. 영어로 'Floyd's Tortoise and Hare'라고 한다. 풀이는 아래와 같은데 1칸 뛰는 말과 2칸 뛰는 말을 계속 돌릴때 순환이 있으면 결국 같은 지점에 오는 순간이 있다는 알고리즘이다. 그에 대한 증명까지는 찾지 못했고 이런 방식으로 찾을 수 있다는 개념까지만 알고가자.

public class Solution {
    public boolean 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;
    }
}

 

참고사이트

• 영어설명: https://www.youtube.com/watch?v=_iB5d55tJMo
• 영어설명: https://www.youtube.com/watch?v=sMqEwkpvJvQ
• 관련없지만 찾다가 발견한: https://www.youtube.com/watch?v=9YTjXqqJEFE
• 유료 알고리즘 공부?사이트: https://www.jomaclass.com/offers/aoewbuYp/checkout

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형