708. Insert into a Sorted Circular Linked List (Linked List)

링크 - https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

이 문제는 prev_node와 node를 사용하여 case들을 잘 나눠 풀어야 하는 문제이다.

1. 먼저 head가 없으면 우리는 자기자신을 도는 node를 만들어 반환한다.

2. 만약 node가 하나밖에 없으면, prev_node와 node가 같으므로 이를 체크해서 하나의 노드를 만들어 집어넣고 끝낸다.

3. 만약 node가 두개 이상이면, 여러개의 케이스들을 점검해봐야한다.

3.1 만약 prev_node.val <= insertVal <= node.val인 상황이면(조건만 맞으면 아무데나 집어넣어도 되므로), 새 노드를 만들어 집어넣고 끝낸다.

3.2 만약 insertVal이 node들의 값보다 크거나 작은 값이라면, node.val < prev_node.val인 상황에서 새 노드를 만들어 집어넣고 끝낸다.

3.3. 만약 이렇게 해도 끝나지 않는다면, 모든 node들의 값이 같은 상황이다. 따라서 prev_node가 head임을 확인하면 새 노드를 집어넣고 끝낸다.

Code

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next
"""

class Solution:
    def insert(self, head: 'Optional[Node]', insertVal: int) -> 'Node':
        if head is None:
            new_node = Node(insertVal)
            new_node.next = new_node
            return new_node

        node = head.next
        prev_node = head

        while node:
            if prev_node == node:
                new_node = Node(insertVal, node)
                node.next = new_node
                break

            if prev_node.val <= insertVal <= node.val or (node.val < prev_node.val and (insertVal <= node.val or insertVal >= prev_node.val)):
                new_node = Node(insertVal, node)
                prev_node.next = new_node
                break

            prev_node = node
            node = node.next

            if prev_node == head:
                new_node = Node(insertVal, node)
                prev_node.next = new_node
                break

        return head

Complexity

Time Complexity: O(N) n개의 노드가 있고 최대 한번을 돈다.

Space Complexity: O(1) pointer 두개를 사용하므로 상수 공간을 사용한다.