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

https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/

 

1. 2022/05/07 시도

소요시간: 25분

class Solution {
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            head = new Node(insertVal);
            head.next = head;
            return head;
        }

        Node prev = head;
        Node current = head;
        while (true) {
            current = current.next;
            if (current == head) {
                Node newNode = new Node(insertVal);
                prev.next = newNode;
                newNode.next = current;
                break;
            }

            if (prev.val > current.val && insertVal <= current.val) {
                Node newNode = new Node(insertVal);
                prev.next = newNode;
                newNode.next = current;
                break;
            } else if (prev.val > current.val && prev.val <= insertVal) {
                Node newNode = new Node(insertVal);
                prev.next = newNode;
                newNode.next = current;
                break;
            } else if (prev.val <= insertVal && insertVal <= current.val) {
                Node newNode = new Node(insertVal);
                prev.next = newNode;
                newNode.next = current;
                break;
            }
            
            prev = current;
        }
        
        return head;
    }
}

풀이 접근 과정

전체적으로 계속 돌리고 조건이 맞을 때 루프를 빠져나오게 한다.
이전 노드를 기억함으로써 사이에 신규노드를 넣을 수 있게 한다.

먼저 한바퀴를 다 돌아도 마땅한 곳이 없을때의 처리를 한다. current ==head
prev는 head로, current.next부터 시작하기 때문에 current = head가 오면 한바퀴를 다 돌았다고 볼 수 있다.

경우의 수에 따라 멈추는 코드를 넣어준다.

 

느낀점

• edge케이스에 대한 문제다. 풀긴 풀었는데 오류가 너무 많아서 다시 풀어봐야겠다.

---

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

반응형