c++ - 将元素插入已排序的循环双链表

Question

我想将一个元素插入到已排序的循环双链表中，这是我尝试过的:

void insertSorted(Node *&head,int x){
    Node *temp = new Node();
    temp->data = x;
    temp->next = temp;
    temp->prev = temp;

    if(head == NULL){
        head = temp;
        return;
    }

    Node *p = head;
    Node *q = NULL;
    do{
        q = p;
        p=p->next;
    }while(p != head && x>p->data);

    if(q == NULL){
        temp->next = head;
        head->prev = temp;
        head = temp;
    }
    else {
        q->next = temp;
        if(p!=NULL){
            temp->next = p;
            p->prev = temp;
        }
        temp->prev = q;
    }
}

代码有效，但问题在于第一个元素每次未排序时，，，例如插入 10 9 8 1 2 ，，，输出将是 10 1 2 8 9 ，，它应该是 1 2 8 9 10

Answer 1

if(q == NULL) 按照您的代码永远不会发生。所以，问题就出现在这里。

当您遇到第一个节点的问题时，条件应该是 (q == head) 并更新 head。您的代码运行正确。