思考:
1.要如何找到插入的點
2.如果head是NULL or head就已經大於data (可以直接插在前面)
3.注意 空指標 的prev問題

DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* llist, int data) {
    DoublyLinkedListNode* newNode = new DoublyLinkedListNode(data);

    if(llist == NULL || llist->data > data){
        newNode->next = llist;
        newNode->prev = NULL;
        if(llist != NULL){
            llist->prev = newNode;
        }
        return newNode;
    }

    DoublyLinkedListNode* current = llist;
    

    while (current->next != NULL && current->next->data < data) {
        //find node, this node->data > data; 
        current = current->next;
    }

    newNode->next = current->next;
    newNode->prev = current;
    
    if (current->next != NULL) {
        current->next->prev = newNode;
    }
    current->next = newNode;

    return llist;
}

DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* llist, int data) {
    DoublyLinkedListNode* node = new DoublyLinkedListNode(data);
    if(llist == NULL || llist->data >= data){
        node->next = llist;
        node->prev = NULL;
        if(llist != NULL){
            llist->prev = node;
        }
        return node;
    }
    DoublyLinkedListNode* ptr = llist;
    //find insert postion
    while(ptr->next != NULL && ptr->next->data < data){
        ptr = ptr->next;
    }
    
    //1 2 4 insert 3, ptr = 2
    //already find node and node->data > data
    node->next = ptr->next;
    node->prev = ptr;
    if(ptr->next != NULL){
        ptr->next->prev = node;
    }
    ptr->next = node;
    return llist;
    
}