вставить в отсортированный список связанных позиций

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

Проще взять пример

10 -> 20 -> 30 -> NULL

Просматривать список двумя указателями: (i) 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. «Вставить» newNode между currentNode и nextNode, выполнив

   2,1 currentNode->next = newNode

   2.2 newNode->next = nextNode

Answer 3

Вы можете использовать рекурсию для обхода односвязного списка назад.

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 4

Вот мое понимание того, что вы спрашиваете: когда вы ищете позицию вставки в односвязном списке, вы обнаруживаете, обнаружив, что вы зашли на один узел слишком далеко, тогда как вернуться назад?

Ну, есть два основных решения:

• заглядывать на один узел вперед при поиске (другой точкой зрения той же идеи является сохранение "конечного" указателя), или

• убедитесь, что есть искусственный хвостовой узел (чтобы у вас всегда был настоящий следующий узел), и чтобы в списке не было других «внешних» указателей, кроме указателя поиска. Вставьте ваш новый узел после узла с более высоким значением. Поменяйте местами содержимое двух узлов.

Второе решение немного хрупко из-за предположения, что в списке нет других «внешних» указателей. Но это отчасти гениально. Я узнал об этом из «Искусства компьютерного программирования» Дональда Кнута.

В качестве альтернативы этим решениям с односвязным списком вы можете просто связать свой список с помощью двойной ссылки.

Приветствия & hth.,

Answer 5

Ни один односвязный список не может вернуться назад.