C++에서 정렬된 순환 연결 리스트에 값 삽입하기

문제 소개

증가 순서로 정렬된 순환 연결 리스트(Circular Linked List)의 한 노드가 주어졌을 때, 새로운 값 insertVal을 리스트에 삽입하되 리스트가 계속 정렬된 상태를 유지하도록 하는 함수를 작성해야 합니다.

여기서 중요한 점은 주어진 노드가 리스트 내 임의의 노드에 대한 참조일 수 있으며, 반드시 시작 노드일 필요는 없다는 것입니다. 삽입 가능한 적절한 위치가 여러 곳이라면 그중 어디에 넣어도 무방합니다. 만약 리스트가 비어 있다면 새 노드 하나로 구성된 순환 리스트를 생성하고 그 노드를 반환해야 하며, 리스트가 비어 있지 않다면 원래 주어진 노드를 그대로 반환하면 됩니다.

예를 들어 리스트가 [3, 4, 1]이고 삽입할 값이 2라면, 결과는 [3, 4, 1, 2]가 됩니다.

해결 전략

이 문제는 다음 단계를 따라 해결할 수 있습니다.

head가 null인 경우
- 주어진 값으로 새 노드를 생성합니다.
- 새 노드의 next가 자기 자신을 가리키도록 설정하여 단일 노드 순환 리스트를 만듭니다.
head가 null이 아닌 경우
- curr을 head의 다음 노드로, prev를 head로 초기화합니다.
- 삽입할 값으로 새 노드 temp를 생성하고, 완료 플래그 done을 false로 설정합니다.
- 무한 루프를 돌며 아래 조건들을 검사합니다.
  - curr->val >= val이고 prev->val <= val이면 일반적인 정렬 위치이므로 prev와 curr 사이에 temp를 삽입한 뒤 루프를 종료합니다.
  - prev->val > curr->val이면 리스트의 순환 지점, 즉 최댓값에서 최솟값으로 넘어가는 경계에 도달한 것입니다. 이때 val이 최댓값 이상이거나 최솟값 이하라면 이 지점에 삽입합니다.
  - curr이 다시 head로 돌아오면 리스트를 한 바퀴 모두 순회한 것이므로 루프를 종료합니다.
  - 위 조건에 해당하지 않으면 prev와 curr을 각각 다음 노드로 이동합니다.
- 루프에서 삽입하지 못한 채(done == false) 빠져나왔다면 리스트의 모든 값이 동일한 경우입니다. 이때는 head 바로 앞에 새 노드를 삽입합니다.
마지막으로 head를 반환합니다.

C++ 구현 예제

아래 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
    int val;
    Node* next;
    Node() {}
    Node(int _val) {
        val = _val;
        next = NULL;
    }
    Node(int _val, Node* _next) {
        val = _val;
        next = _next;
    }
};
class Solution {
public:
    Node* insert(Node* head, int val) {
        if(!head){
            head = new Node(val);
            head->next = head;
        }
        else{
            Node* curr = head->next;
            Node* prev = head;
            Node* temp = new Node(val);
            bool done = false;
            while(1){
                if (curr->val >= val && prev->val <= val) {
                    prev->next = temp;
                    temp->next = curr;
                    done = true;
                    break;
                }
                if (prev->val > curr->val) {
                    if (prev->val <= val || val <= curr->val) {
                        prev->next = temp;
                        temp->next = curr;
                        done = true;
                        break;
                    }
                }
                if (curr == head)
                    break;
                prev = curr;
                curr = curr->next;
            }
            if(!done){
                temp->next = head;
                prev->next = temp;
                head = temp;
            }
        }
        return head;
    }
};
main(){
    Solution ob;
    Node *head = new Node(3);
    head->next = new Node(4);
    head->next->next = new Node(1, head);
    ob.insert(head, 2);
    Node *temp = head;
    if (head != NULL){
        do{
            cout << temp->val << " ";
            temp = temp->next;
        }
        while (temp != head);
    }
}

핵심 포인트 정리

이 알고리즘의 시간 복잡도는 리스트를 최대 한 바퀴 순회하므로 O(n)이며, 추가 공간은 새 노드 하나뿐이므로 공간 복잡도는 O(1)입니다. 특히 두 가지 삽입 조건을 구분하는 것이 핵심입니다. 첫 번째 조건은 일반적인 오름차순 구간에서의 삽입을 처리하고, 두 번째 조건은 순환 리스트 특유의 '내림→오름' 경계 지점에서의 삽입을 처리합니다. 마지막으로 모든 노드의 값이 같은 특수한 경우에는 어디에 삽입해도 정렬이 유지되므로 head 앞에 붙여 해결합니다.

입력

node *head = new Node(3);
head->next = new Node(4);
head->next->next = new Node(1, head);
insertVal = 2

출력

3 4 1 2