Insert into a Sorted Circular Linked List – แทรกค่าใน Circular Linked List เรียงลำดับ C++

ปัญหา: Insert into a Sorted Circular Linked List

กำหนดโหนดอ้างอิงจาก Circular Linked List ที่เรียงเพิ่มขึ้น แทรกค่า insertVal ให้ยังคงเป็น sorted circular list
โหนดอ้างอิงอาจไม่ใช่หัว (head) ถ้ารายการว่าง → สร้างโหนดเดี่ยว circular

ตัวอย่าง

List: 3 → 4 → 1 → (กลับ 3), insertVal = 2
Result: 3 → 4 → 1 → 2 → (กลับ 3)

แนวทางแก้ปัญหา

กรณีที่เป็นไปได้

1. List ว่าง: สร้างโหนดใหม่ next ชี้ตัวเอง
2. ปกติ (มีจุดตัดปกติ): หา prev ≤ val ≤ curr → แทรกระหว่าง prev และ curr
3. จุดต่อท้าย-หัว (wrap-around): prev->val > curr->val (จุดที่ค่ามากสุดติดค่าน้อยสุด)
   • ถ้า val ≥ prev->val (มากกว่าสูงสุด) หรือ val ≤ curr->val (น้อยกว่าต่ำสุด) → แทรกที่นี่
4. ทุกค่าเท่ากัน / วนครบรอบไม่เจอจุดแทรก: แทรกหลัง head (หรือทุกที่ก็ได้)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node() {}
    Node(int _val) : val(_val), next(nullptr) {}
    Node(int _val, Node* _next) : val(_val), next(_next) {}
};

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) {
            head = new Node(insertVal);
            head->next = head;
            return head;
        }

        Node* prev = head;
        Node* curr = head->next;

        while (true) {
            // Case 1: Normal insertion point
            if (prev->val <= insertVal && insertVal <= curr->val) {
                break;
            }
            // Case 2: Wrap-around point (max -> min)
            if (prev->val > curr->val) {
                if (insertVal >= prev->val || insertVal <= curr->val)
                    break;
            }
            // Case 3: Back to head (all same value or not found)
            if (curr == head) break;

            prev = curr;
            curr = curr->next;
        }

        prev->next = new Node(insertVal, curr);
        return head;
    }
};

// Helper: print circular list
void printList(Node* head) {
    if (!head) return;
    Node* cur = head;
    do {
        cout << cur->val << " ";
        cur = cur->next;
    } while (cur != head);
    cout << '\n';
}

int main() {
    Solution ob;
    Node* head = new Node(3);
    head->next = new Node(4);
    head->next->next = new Node(1, head); // circular

    head = ob.insert(head, 2);
    printList(head); // 3 4 1 2
    return 0;
}

ความซับซ้อน

• เวลา: O(N) – ตรวจสอบสูงสุด 1 รอบ
• พื้นที่: O(1)

ข้อสังเกต

• LeetCode 708
• จัดการกรณี wrap-around (max→min) เป็นหัวใจสำคัญ
• กรณีค่าทั้งหมดเท่ากัน (เช่น 3→3→3) → curr==head จะ break → แทรกหลัง head
• โค้ดต้นฉบับใช้ done flag และ logic ซับซ้อนกว่า – วิธีนี้สะอาดกว่า