2 분 소요

Linked List

문제

문제 링크

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

스스로 고민

접근법

  • 문제 자체는 간단한다 링크드 리스트가 순환하는지 하지 않는지에 대해 참과 거짓으로 반환하면 된다.
  • 진짜 문제는 링크드 리스트에 대해 개념적으로만 이해하고 실제로 어떻게 활용해야되는지 감이 오지 않았다.
    • 보통 리스트 자체가 배열과 링크드 리스트의 특성을 모두 갖고 있고 장고 에서 사용하는 orm 구조상 일반적으로 잘 사용할 일이 없어서 감이 잘 안왔다.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# 링크드 리스트 생성
node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)

# 순환 부분 설정
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2
  • 이런 식으로 노드들이 연결된다
  • 각 노드들을 부르면 각각 다른 메모리 주소를 갖고 있으며 next 는 다음 노드의 주소를 가리킨다.
  • 사실 위와 같이 구현된다면 3,2,0, -4 이런 벨류 값은 현재 문제에서 무의미 하다
  • 순환이 되는지 안되는지만 확인하면 된다.

의사코드

  • 순환을 확인해야되기 때문에 두 개의 변수를 지정해준다.
  • fast, slow 두 개의 변수를 선언해준다.
  • while 문을 통해 fast 와 fast.next 두 개다 none 이 아닐 경우 계속 진행시킨다.
    • 처음 fast는 head의 초기 값인데 뒤에 next 값이 있는지 확인
  • slow 는 한 칸 씩 이동 fast는 두 칸씩 이동 시킨다.
  • 순환이 이루어진다면 두 개 값이 만날 거고 만나는 경우 True를 반환

구현 코드

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

시간 복잡도와 공간 복잡도

시간 복잡도:

  • slow와 fast 포인터 모두 한 번의 반복문 안에서 링크드 리스트를 순환하게 된다. 이때 fast 포인터는 두 칸씩 이동하므로 전체 링크드 리스트의 길이를 n이라고 할 때, fast 포인터는 최대 n/2 번 이동하게 된다.
  • 따라서 반복문의 실행 횟수는 대략 n/2 번 정도가 된다. 이는 O(n)의 시간 복잡도를 가진다.

공간 복잡도:

  • slow 포인터와 fast 포인터, 그리고 상수 개수의 변수들만 사용되므로, 추가적인 공간이 링크드 리스트의 크기에 비례하지 않는다. 즉, 공간 복잡도는 O(1)입니다.

회고 과정

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        visited = set() 

        while head: 
            if head in visited:
                return True
            visited.add(head)
            head = head.next

        return False
  • 중복 값이 없도록 visited 라는 변수의 집합을 선언해준다.
  • head는 none 값이 없는 이상 계속 반복이 된다.
  • visited 안에 head를 차곡차곡 쌓아준다.

  • visited 안에 head 값이 존재하게 되면 반복이 증명되므로 True 반환

  • 코드 설명없이 가독성만 보면 위의 코드가 더 좋을 수도 있다고 생각했다.
  • 성능과 가독성 두 가지 모두 고려해서 좀 더 나은 방향이 있는지 항상 고민해보는 습관을 가져야겠다고 생각했다.

댓글남기기

참고