首页 > 代码库 > 给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。

给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。

2024-11-14 01:44:39   202人阅读

链表结构如下：

typedef struct Node{
    int num;
    struct Node *next;
}NodeHead,*Nodes;

删除函数如下：

void DeleteNode(Nodes head,Nodes target)

很简单的想法就是，要删除该结点，可以把该结点的下一个结点的值赋给该结点，接着删除下一个结点即可。

但要考虑三种情况，一是该结点是尾结点，二是除了头结点以外，只有一个结点，三是只有头结点，不过这样那就直接返回就可以啦。

以下是代码，很简单，就不需要注释了，只要把以上三种情况都考虑进去，就可以了。

#include <stdio.h>
#include <string.h>

typedef struct Node{
    int num;
    struct Node *next;
}NodeHead,*Nodes;

void DeleteNode(Nodes head,Nodes target){
    
    if(head->next==NULL)
        return ;
    if(target->next==NULL){
        if(head->next==target){
            head->next = NULL;
            free(target);
        }else{
            Nodes tmp = head->next;
            while(tmp->next!=target){
                tmp = tmp->next;
            }
            tmp->next = NULL;
            free(target);
        }
        return ;
    }
    Nodes tmp = target->next;
    target->num = tmp->num;
    target->next = tmp->next;
    free(tmp);
    
}

void main()
{
    
    Nodes head = NULL;
     head = (Nodes)malloc(sizeof(NodeHead));
    head->next = NULL;
    int i ;
    for(i = 0 ;i < 4 ; i++){
        Nodes node = (Nodes)malloc(sizeof(NodeHead));
        node->num = i;
        node->next = head->next;
        head->next = node;
    }
    Nodes tmp;
    tmp = head->next;
    tmp = tmp->next;
    tmp = tmp->next;
    DeleteNode(head,tmp);
    
    
    Nodes tmp2;
    tmp2 = head->next;
    for(i = 0 ; i <3 ; i++){
        printf("%d",tmp2->num);
        tmp2 = tmp2->next;
    }

    
    return 0;
}

 

给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。


联系
我们