[1스4코2파] # 200 LeetCode 141. Linked List Cycle

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (200차)
[4코1파] 2023.01.13~ (192일차)
[1스4코1파] 2023.04.12~ (103일차)
[1스4코2파] 2023.05.03 ~ (81일차)

Today :

2023.07.22 [200일차]
Linked list
141. Linked List Cycle

141. Linked List Cycle

https://leetcode.com/problems/time-based-key-value-store/description/

문제 설명

주어진 linked list가 순환하는지 확인 하는 문제이다.
같이 주어진 pos는 마지막 linked list와 연결된 노드의 인덱스를 나타내는데 사용되므로, 순환이 된다면 true, 아니면 false를 return 함!

문제 풀이 방법

노드의 값을 복사하는 것은 깊은 복사로 하는데,
random 노드를 기존 리스트와, 새 리스트에 해당하는 노드포인터와, 순서를 해시테이블에 저장하고. 이를 이용해 새로운 리스트의 각 노드의 ramdom포인터를 구해야 한다.

두 개의 해시테이블의 key, value순서가 서로 다르기 때문에, 저장된 해시테이블에서 순서에 따른 노드를 바로 얻는다.
원본리스트와 새 리스트의 같은순서의 노드를 서로 mapping 시켜 놓는 식으로 구현한다.

내 코드

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
            
        return False

증빙

여담

토요일 아침을 여는 linked list ~ ㅂㄹ~!
제 칭구 고양이보세요