如何删除单链表中的任意节点

Question

这是我的代码：

#include<stdio.h>
#include<stdlib.h>

struct node
{ 
    int x;
    struct node *next;       
};

struct node *addNode(struct node *head, int y)
{
       struct node *traverser;
       traverser = head;
       if(traverser!=NULL)
       {                 
             while(traverser->next!=NULL)
             traverser=traverser->next;

             traverser -> next = malloc(sizeof(struct node));
             traverser -> next -> x = y;
             traverser -> next -> next = NULL;
       }
       else
       {
             head= malloc(sizeof(struct node));
             head -> x=y;
             head -> next = NULL;
       }    
       return head;
 }

 void display(struct node *head)
 {   
     struct node *traverser;
     traverser = head;

     while(traverser!=NULL)
     {
          printf("%d\n",traverser->x);
          traverser=traverser->next; 
     }
 }

 struct node *InitializeList(void)
 {
       return NULL;
 }

int main()
{
    struct node *head;
    head = InitializeList();
    head = addNode(head,2);
    head = addNode(head,15);
    head = addNode(head,5);
    head = addNode(head,8);
    display(head);  

    free(head);
    getchar();
}

我需要像这样删除 main 中的一个节点

struct node *head;
head = InitializeList();
head = addNode(head,2);
head = addNode(head,15);
head = addNode(head,5);
head = addNode(head,8);
display(head);  
removenode(5);
display(head);  
removenode(8); 
display(head);  
free(head);

这是我在删除程序中的特定节点时的 main() 代码。

但我该怎么办呢？ removenode() 只是函数名称我应该使用什么算法？或者什么或如何删除它？

Answer 1

不是一个完整的答案，只是一些一般建议

为了弄清楚这种事情，通常只需解决三种情况就足够了

• 要删除的节点是头
• 要删除的节点是尾
• 要删除的节点 确保

---

您将遇到的最大麻烦来源是

• 任何前面节点中的“下一个”字段得到正确重置，
• 以确保调用者获得或保留指向 有效 指针em>新的头。

请注意，有一个递归实现（例如n.next = remove(n.next,val)）使这两个问题变得相同，并且您可以将其主要转换为循环防止很长的列表上的堆栈溢出。

---

可能出现的一个子问题是在列表中找到要删除的节点。您可以通过将查找目标节点的部分与 remove(node* head, node* target) 分开来让您的生活变得更轻松吗？

Answer 2

算法原型需要是：

struct node * removenode(struct node *head, int y);

因为如果删除第一项，原始的“头”指针将不再有效。

该算法只是逐步浏览列表，记住前一项（和头部），然后查找数据。找到后，将前一项的下一个指针设置为当前项的下一项。

Answer 3

从较高层次来看，要删除任何节点，您需要做的是：

1) 指向指向您要删除的节点的项目。

2) 将要删除的项目的引用设置为要删除的项目的下一个项目。

3) 删除要删除的项目。

这样，您的链就得到了维护，并且您已经从内存中释放了该元素。

就像这样：

Head -> Item1 -> Item2 -> Item3 -> NULL

如果你想删除 Item2，你可以这样做：

Head -> Item1 -> Item2 -> Item3 -> NULL
          ^       ^   (Grab pointers to these items)

将 Item1 的旁边设置为 Item2 的下一个，然后删除 Item2。

           /--------------\
Head -> Item1    Item2 -> Item3 -> NULL
          ^       ^ (Delete 2)

编辑：删除项目或项目3：

Head -> Item1 -> Item2 -> Item3 -> NULL
 ^       ^   (Grab pointers to these items)

将头部重新指向项目2，然后删除项目1：

   /--------------\
Head    Item1 -> Item2 -> Item3 -> NULL
 ^       ^ (Delete 1)

或

Head -> Item1 -> Item2 -> Item3 -> NULL
                    ^       ^   (Grab pointers to these items)

将头部重新指向项目2，然后删除项目1：

                    /--------------\
Head -> Item1 -> Item2   Item3 -> NULL
                   ^       ^ (Delete 3)

Answer 4

看看这是否适合你，也许存储在我的电脑中的某个地方，用于这样的情况：

void RemoveNode(struct node*x)
{
    struct node *temp=x,*tempo=NULL;
    int i=0,n;
    printf("\nWould you like to delete a node?\nPress 1 for Yes 2 for No: ");
    scanf("%d",&i);
    if(i==1)
    {
        printf("Enter nth node to be deleted");
        scanf("%d",&n);
        i=0;
        if(n==1)
        {
        x=temp->next;
        free(temp);
        }
        while(i<n-2)
        {
        temp=temp->next;
        i++;
        }
        if(temp->next->next==NULL)
        {
        tempo=temp->next;
        temp->next=NULL;
        free(tempo);
        }
        else
        {
        tempo=temp->next;
        temp->next=temp->next->next;
        free(tempo);
        }
    }
    else
    printf("\n No Changes Made\nExiting....");
}

它总是最重要的。