добавить элемент после элемента specialiec в связанном списке и удалить первый элемент

Question

Я попытался решить эту проблему, но мне удалось ее частично решить.

Моя проблема в этом методе является то, что мне нужно, чтобы добавить элемент после другого элемента:

Пример: add 5 1

5 представляет собой элемент в связанном списке, но я хочу добавить 1 после того, как 5 .

Пример: пусть связанный список содержит следующие элементы: 2 3 7

я называю метод, чтобы добавить 1 AFTE r 3, add 3 1, поэтому результат должен быть 2 3 1 7, но с моим методом результат 2 1 3 7, что является моей проблемой.

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

Пример: add 2 1

Он действует как если первый элемент не существует:

void addNodeAtPos(link *head, int pos,int addelement) 
{ 
    link prev=NULL; 

    link curr =*head; 

    link newNode = (link)malloc(sizeof(node)); 

    newNode->data = addelement; 


    while(curr->next != NULL) 
    { 

       prev = curr; 
     curr = curr->next; 


     if(curr->data == pos) 
    { 

     newNode->next = curr; 
     prev->next = newNode; 

     break; 
    } 
    } 

    } 

Мои проблема заключается в том, что я не могу удалить первый элемент:

void deletenode(link *head,int s){ 

    bool found = false; 

    node *curr = *head, *prev=NULL; 

    while(curr != NULL){ 

     // match found, delete 
     if(curr->data == s){ 

      found = true; 
      // found at top 

      if(prev == NULL){ 

       link temp = *head; 

       curr->next= prev; 
       delete(temp); 
       // found in list - not top 
      }else{ 
       prev->next = curr->next; 
       delete(curr); 
      } } 
     // not found, advance pointers 
     if(!found){ 
      prev = curr; 
      curr = curr->next; } 
     // found, exit loop 
     else curr = NULL; } 




    } 

Answer 1

Вот решение первой задачи

if(curr->data == pos) 
{ 
    // tempNode = curr->next; 
    // improvement as suggested by @Rerito 
    newNode->next = curr->next; 
    curr->next = newNode; 
    break; 
} 

Answer 2

Похоже, вы используете некруглые дважды связанные списки. Таким образом, оба конца списка отмечены NULL. Теперь мне кажется, что вы используете C++ в очень C-esque ... (NULL не будет использоваться в C++, есть ключевое слово nullptr).

Я буду решать ваши проблемы, предполагая, что вы используете C вместо C++.

// Note that I pass a link **ptr, NOT a link *ptr ... 
void addNodeAtPos(link **head, int pos, int addelement) { 
    // I am assuming head will be a valid pointer, if not, please add the appropriate checks. 
    link *newNode = NULL, *cur = *head; 
    if (NULL == (newNode = malloc(sizeof(link))) 
     return; 
    newNode->data = addelement; 
    while (cur != NULL) { 
     if (cur->data == pos || NULL == cur->next) { 
      newNode->next = cur->next; 
      newNode->prev = cur; // remove this line if there is no prev pointer. 
      cur->next = newNode; 
      if (NULL != newNode->next) { // remove this if clause if there is no prev pointer 
       newNode->next->prev = newNode; 
      } 
      break; 
     } 
     cur = cur->next; 
    } 
} 

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

Теперь, рассматривая проблему удаления первого элемента:

void deleteNode(link **head, int el) 
{ 
    // I assume you wont pass a `NULL` ptr as @head 
    link *cur = *head, *prev = NULL; 
    while (cur != NULL) { 
     if (cur->data == el) { 
      next = cur->next; 
      prev = cur->prev; 
      free(cur); 
      if (NULL != next) 
       next->prev = prev; 
      if (NULL != prev) 
       prev->next = next; 
      else 
       *head = next; 
      break; 
     } 
     cur = cur->next; 
    } 
} 

Зачем вам нужно пройти link **head вместо link *head? Поскольку, когда вы удаляете головку списка, вы должны убедиться, что он больше не будет доступен, и вам необходимо обновить указатель на голову, который вы используете в другом месте. Это то, что сделано в заявлении *head = next; в приведенной выше функции.

Если вы используете односвязанны список (только указатель на следующий элемент, а не предыдущий), решение становится следующее:

void deleteNode(link **head, int el) 
{ 
    // I assume you wont pass a `NULL` ptr as @head 
    link *cur = *head, *prev = NULL, *next = NULL; 
    while (cur != NULL) { 
     if (cur->data == el) { 
      if (NULL != prev) 
       prev->next = cur->next; 
      else 
       *head = cur->next; 
      free(cur); 
      break; 
     } 
     prev = cur; 
     cur = cur->next; 
    } 
}