插入到已排序位置的链表

Question

我有一个与我不久前问过的问题非常相关的问题

放置一个立即在排序位置中插入值

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

如果可能的话，如何向后循环链表？我无法弄清楚，因为这似乎不可能，因为它应该是双重链接列表，那么如果我没有错的话？无论如何，我正在使用单链表。

编辑

我想我会采用前瞻性方法，这就是我到目前为止所做的。我陷入了如何保存前一个（键，值）的困境。这是到目前为止已完成的代码。 for循环用于寻找我想要插入的位置。我有向前看的能力，如果到达终点，它就会破裂。

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

用两个指针遍历列表：(i) currentNode 和 (ii) nextNode 。

从 currentNode = NULL 和 nextNode = <10> 开始。将它们循环向前移动，只要 nextNode->key < insertkey 为 true。

退出循环时（例如：for insertKey == 25, currentNode = <20>, nextNode = <30​​>）：

1. create newNode with newNode->key = insertKey 和 newNode->value = insertValue

2. 在 currentNode 和 nextNode 之间“插入”newNode代码>通过做

   2.1 currentNode->next = newNode

   2.2 newNode->next = nextNode