插入到排序的位置鏈表

Question

我有問題，相當多的與此相關的，我問前一陣子

place a value in the sorted position immediately

我不知道你是否能在使用同樣的方法，你在一個鏈表退步找到它應該插入的位置。

如果可能的話你怎麼循環鏈表落後？我無法弄清楚，因爲它似乎不可能，因爲它應該是一個雙鏈接列出，如果我沒有錯，然後呢？無論如何，我正在與單鏈表。

編輯

我想我會爲期待的做法，這是我迄今所取得。我堅持在這一點上我應該如何保存以前的（鍵，值）。這是迄今所做的代碼。 for循環用於查找我想要插入的位置。而且我向前看，如果它達到目的就會破裂。

OK，到目前爲止，現在我想插入值到正確的位置。它在這裏我卡住了。應該怎麼做？現在，當我插入鑰匙：2, 1, 0, 3，它只會打印出1, 3

struct my_list 
{ 
    /* a pointer to the first element of the list */ 
    struct list_link* first; 
}; 

struct list_link 
{ 
    int key;    // identifies the data 
    double value;   // the data stored 
    struct list_link* next; // a pointer to the next data 
}; 

struct list_link* create(int key, double value, struct list_link* next) 
{ 
    // creates the node; 
    struct list_link * new_link; 
    new_link = new struct list_link; 

    // add values to the node; 
    new_link->key = key; 
    new_link->value = value; 
    new_link->next = next; 

    return new_link; // Replace this, it is just to be able to compile this file 
} 

void list_insert(struct my_list* my_this, int key, double value) 
{ 
    if(my_this->first == NULL) // add if list empty 
     my_this->first = create(key, value, my_this->first); 
    else 
    {  
     struct my_list* curr; 
     struct my_list* prev;   
     struct my_list start; 

     start.first = my_this->first; 
     curr = my_this; 

     cout << "Too be appended: "; 
     cout << key << " " << value << endl; 
     for(curr->first = my_this->first; 
      key > curr->first->key; 
      curr->first = curr->first->next) 
     { 
     if(curr->first->next == NULL) //peek at front if empty 
      break; 
     } 
     cout << "append here " << key << " > " << 
      curr->first->key << endl << endl; 
     //perform some surgery 
     if(curr->first->next == NULL) 
     {  
     curr->first->next = create(key, value, my_this->first->next); 
     } 
     else 
     {  
     curr->first = start.first; //move back to start of list 
     my_this->first = create(key, value, my_this->first); 
     }  
    } 
} 

Answer 1

無法遍歷單鏈表落後，但你可以保持一個指向你所看到的，而不只是一個最後的兩個元素。

所以，遍歷從前面的列表，並保持兩個指針：當前和以前的。如果要插入的元素少於當前元素，則更新上一個元素指向它。

Answer 2

沒有一個單向鏈表不能倒退。

Answer 3

這裏是我的什麼你問的理解：當你在一個單向鏈表搜索插入位置，你的發現，你已經走了一個節點太遠，那麼，怎麼回去找呢？

好，主要有兩種解決方案：

• 偷看一個節點提前，而搜索（同樣的想法的不同觀點是保持一個「尾隨」指針），或

• 化妝確保有一個人爲的尾節點（這樣你總是有一個真正的下一個節點），並且沒有其他的「外部」指針進入列表中的搜索指針。將新節點插入具有較高值的​​節點之後。交換兩個節點的內容。

第二個解決方案有點脆弱，因爲假設沒有其他「外部」指針進入列表。但它有點巧妙。我從Donald Knuth的「計算機程序設計藝術」中學到了它。

或者這些單向鏈表的解決方案，你可以雙鏈接列表。

乾杯&心連心，

Answer 4

您可以使用遞歸遍歷向後單鏈表。

void traverse_backwards(NODE node) 
{ 
    if (node->next != null && !node->is_marked) 
    { 
     node->is_marked = 1; 
     traverse_backwards(node->next); 
    } 
    else 
    { 
     // logic goes here 
    } 
} 

Answer 5

其容易採取的示例

10 -> 20 -> 30 -> NULL 

遍歷列表與兩個指針：（ⅰ）currentNode和（ii）nextNode。

以currentNode = NULL和nextNode = <10>開頭。只要nextNode->key < insertkey爲真，就將它們都向前移動循環。

退出時從循環（例如：insertKey == 25, currentNode = <20>, nextNode = <30>）：

1. 創建newNode與newNode->key = insertKey和newNode->value = insertValue

2. 通過執行

   2.1 currentNode->next = newNode

   「插入」 currentNode和nextNode之間newNode

   2.2 newNode->next = nextNode