Блог

Возникли проблемы со связанным списком. Нужно создать метод, который заменит данные в списке, не создавая новый элемент, а изменяя указатели. На данный момент у меня есть такой метод:

 void replaceValues(Node* head, int indexOne, int indexTwo)  {  Node* temporaryOne = NULL;  Node* temporaryTwo = NULL;  Node* temp = NULL;  Node* current = head;  int count = 0;  while (current != NULL) {  if (count == indexOne)  {  temporaryOne = current;  }  else if (count == indexTwo)  {  temporaryTwo = current;  }  count  ;  current = current-gt;next;  }  current = head;  count = 0;  while (current != NULL) {  if (count == indexOne)  {  head = temporaryTwo;  }  else if (count == indexTwo)  {  head = temporaryOne;  }  count  ;  current = current-gt;next;  } }  

Я уверен, что существует более простой способ, как это сделать, но я не до конца понимаю, как это работает… Заранее спасибо за помощь.

Я предполагаю, что под «заменой» вы на самом деле подразумеваете «обмен»/»обмен».

Некоторые вопросы:

• Аргумент head должен передаваться по ссылке, так как один из узлов для подкачки на самом деле может быть головным узлом, а затем head должен ссылаться на другой узел после того, как функция выполнит свою работу.
• Предыдущему узлу temporaryOne потребуется next изменить указатель, поэтому вы должны остановить свои циклы на один шаг раньше, чтобы получить доступ к этому узлу и сделать это.

  
  

• В некоторых случаях head может потребоваться изменение, но это, безусловно, не всегда так, поэтому делать head = temporaryOne или head = temporaryTwo , безусловно, неправильно. В большинстве случаев вам нужно будет подключиться к измененному узлу с предыдущего узла (см. Предыдущий пункт).
• next Указатель заменяемого узла также необходимо будет изменить, так как следующий за ним узел будет отличаться от предыдущего.

Как уже упоминалось в комментариях, рекомендуется разделить задачу на удаление и вставку, так как next работа с указателями может привести к путанице, когда вы пытаетесь охватить все возможные случаи, в частности, проводя различие между случаем, когда два узла смежны, а когда нет.

 Node* removeNode(Node* amp;head, int index) {  // If index is out of range, no node is removed, and function returns nullptr  // Otherwise the extracted node is returned.  if (head == nullptr || index lt; 0) return nullptr;  Node* current = head;  if (index == 0) {  head = head-gt;next;  current-gt;next = nullptr;  return current;  }  while (--index gt; 0) {  current = current-gt;next;  if (current == nullptr) return nullptr;  }  Node* temp = current-gt;next;  if (temp != nullptr) {  current-gt;next = temp-gt;next;  temp-gt;next = nullptr;  }  return temp; }  void insertNode(Node* amp;head, Node* node, int index) {  // If index is too large, node is inserted at the end of the list  // If index is negative, node is inserted at the head of the list  if (index lt;= 0 || head == nullptr) {  node-gt;next = head;  head = node;  return;  }  Node* current = head;  while (--index gt; 0 amp;amp; current-gt;next != nullptr) {  current = current-gt;next;  }  node-gt;next = current-gt;next;  current-gt;next = node; }  bool exchangeNodes(Node* amp;head, int indexOne, int indexTwo) {  // Returns true when successful, false when at least one index   // was out of range, or the two indexes were the same  if (head == NULL || head-gt;next == NULL || indexOne == indexTwo || indexOne lt; 0) return false;  // To ensure the right order of operations, require the first index is the lesser:  if (indexOne gt; indexTwo) return exchangeNodes(head, indexTwo, indexOne);  Node* two = removeNode(head, indexTwo);  if (two == nullptr) return false; // out of range  Node* one = removeNode(head, indexOne);  insertNode(head, two, indexOne);  insertNode(head, one, indexTwo);  return true; }