如何在頭部內的特定節點之後插入鏈表？ 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

你要記住你是後插入的節點，並具有節點鏈接到新的一個。

例如，在循環地發現，來後temp，current，有另一個變量，說prev，只是current = current->next之前做pre = current的節點。

Answer 2

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 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; 
 
     } 
 
    } 
 
}