在链接列表中的特定元素之后添加元素并删除第一个元素

Question

我努力解决这个问题，但只设法部分解决它。

我在这个方法的问题是，我需要另一个元素的后面添加一个元素：

例子：add 5 1

5是链表的元素，但我想5后加1 。

实施例：设链表包含这些元素：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++ ......（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; 
    } 
}