c++ - 插入到排序位置链表

Question

我有一个问题与我刚才问的这个问题非常相关

place a value in the sorted position immediately

我想知道你是否可以使用相同的方法，在链表中向后退一步，找到它应该插入的位置。

如果可能，你如何向后循环链表？我想不通，因为它似乎不可能，因为它应该是双链接列表，如果我没记错的话？无论如何，我正在使用单向链表。

编辑

我想我会采用前瞻性方法，这是我目前所做的。我一直停留在我应该如何保存前一个(键，值)的问题上。这是到目前为止所做的代码。 for 循环用于查找我要插入的位置。我有 peek forward，它会在它到达尽头时中断。

到目前为止，我想将值插入到正确的位置。我被困在这里。应该怎么做？现在当我插入键: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

您不能向后遍历单链表，但您可以保留一个指向您看到的最后两个元素的指针，而不是一个。

所以，从前面遍历链表，保留两个指针:current和previous。如果您要插入的元素小于当前元素，则更新 previous 以指向它。