如何在head中的特定节点后插入链表?c++

Question

我编写了以下代码，将一个整数插入到链表中，但采用了排序方法。

我评论了我的问题所在，并在下面进行了解释：

void LLL::insertSorted(int r) {
    node * temp = NULL;
    node * current = NULL;
    if (head == NULL) {
        head = new node;
        head->data = r;
        head->next = NULL;
    } else {
        temp = new node;
        temp->data = r;
        current = head;
        while (temp->data > current->data && current != NULL) {
            current = current->next;
        }
        temp->next = current;
        /* 
         * Assume that I have head points to this list: { 3 -> 5 -> 8 -> NULL }
         * And I want to insert {6} (temp) to the list just after 5; then what 
         * I've done so far on my previous code I made temp = {6 -> 8 -> NULL}.
         * NOW!! How can correctly insert temp to ((head)) just after {5}??!
         */
    }
}

Answer 1

void LLL::insertSorted(int r) {
    node * cur = head;
    node * prev = NULL;
    while((cur != NULL) && (r > cur->data)){//find the location to insert
        prev = cur;
        cur = cur->next;
    }
    node *new_node = new node;
    new_node->data = r;
    new_node->next = cur;
    if(prev == NULL){//new first one
        head = new_node;
    }else{
        prev->next = new_node;
    }
}

Answer 2

您需要记住在哪个节点之后插入，并使该节点链接到新节点。

例如，在循环中查找temp、current之后的节点，使用另一个变量prev，并在current = current->next之前执行pre = current。

Answer 3

插入时需要一个新节点
我认为只需在您想要插入的上一个节点之后创建一个新节点，如注释中的5

Answer 4

这是最终结果：（有效！）它处理以下情况：

• 情况1：头部是空的
• 情况2：新元素是列表中最小的
• 情况3：新元素位于列表的中间位置
• 情况4：新元素是最大的

void LLL::insertSorted(int r) {
    node * temp = NULL;
    node * current = NULL;
    node * previous = NULL;
    if (head == NULL) {
        head = new node;
        head->data = r;
        head->next = NULL;
    } else {
        temp = new node;
        temp->data = r;
        temp->next = NULL;
        current = head;
        if (temp->data < current->data) {
            temp->next = head;
            head = temp;
        } else {
            while (current != NULL && temp->data >= current->data) {
                previous = current;
                current = current->next;
            }
            temp->next = current;
            previous->next = temp;
        }
    }
}