[Python] LeetCode - Linked List Cycle 2

Problem

 

Solving Process

 

이 문제는 결국 내 힘으로는 못 풀었던 문제이다... ㅠㅡㅠ

약 두시간 동안 고민했으나 에러만 잔뜩 맞이하고 결국 답을 참조했던 문제

 

푸는 방법은 

1. 각 노드의 값을 dict, set 등에 저장 한 후 중복을 검사

2. two pointers를 사용해 돌면서 나아가는 방식

 

둘의 시간 복잡도는 O(n)으로 같지만

공간복잡도는 1. O(n) 2.O(1)으로 두번째 방법이 제일 효율적이다.

 

Solution

class Solution:
    # O(n) time and O(n) space
    def detectCycle(self, head: ListNode) -> ListNode:
        dictionary = collections.defaultdict(ListNode) #or can use set
        while(head):
            if head in dictionary:
                return head
            dictionary[head] = True
            head = head.next
        return None

class Solution:	
    #O(n) time and O(1) space
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
            if slow==fast:
            	slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
        	return slow
        return None

 

알고리즘의 길은 멀고도 험하다 ..~ .~ ㅠ