Chèn vào danh sách liên kết vòng đã sắp xếp trong C++

Giới thiệu

Cho một nút của danh sách liên kết vòng (circular linked list) đã sắp xếp tăng dần. Chèn giá trị insertVal sao cho danh sách vẫn sắp xếp. Trả về nút gốc (hoặc nút mới nếu danh sách rỗng).

Thuật toán

1. Nếu rỗng: tạo nút mới trỏ vào chính nó, trả về.
2. Duyệt vòng từ head:
   • Tìm vị trí prev->val <= val <= curr->val (trường hợp thường).
   • Hoặc vị trí "ngắt" của vòng: prev->val > curr->val (điểm chuyển từ max về min). Tại đây chèn nếu val >= prev->val (lớn nhất mới) HOẶC val <= curr->val (nhỏ nhất mới).
3. Nếu duyệt hết vòng không chèn được (tất cả giá trị bằng nhau) → chèn sau head.

Cài đặt 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 val) {
        if (!head) {
            head = new Node(val);
            head->next = head;
            return head;
        }
        Node* prev = head;
        Node* curr = head->next;
        while (true) {
            if (prev->val <= val && val <= curr->val) break; // giữa
            if (prev->val > curr->val) { // ngắt vòng
                if (val >= prev->val || val <= curr->val) break;
            }
            prev = curr;
            curr = curr->next;
            if (curr == head) break; // hết vòng
        }
        prev->next = new Node(val, curr);
        return head;
    }
};

Ví dụ

Danh sách: 3 → 4 → 1 → (quay về 3). Chèn 2.

Kết quả: 3 → 4 → 1 → 2 → (quay về 3).

Độ phức tạp

• Thời gian: O(N) – duyệt tối đa 1 vòng.
• Không gian: O(1).

LeetCode 708 "Insert into a Sorted Circular Linked List".