面试题 13

1 题目描述

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

2 解法描述

1. 常规情况下，需要遍历整个链表，找到待删节点的前驱节点，然后将前驱节点的 next 指针指向待删节点的 next 指针指向的位置。时间复杂度为 O(n)
2. O(1) 时间复杂度解法，待删节点复制其后继节点的值，然后将后继节点删掉。

3 解法 2 实现

一般情况：待删节点位于链表的中间位置
特殊情况：待删节点位于链表的尾部

#include<stdio.h>
typedef int ElemType;
typedef struct node{
    ElemType data;
    struct node* next;
}LNode,*LinkList;

void createList_tail(LinkList *L){
    ElemType temp;
    LNode* p,*r;
    *L =(LinkList) malloc (sizeof(LNode));
    (*L)->next=NULL;
    (*L)->data=-1;
    r=(*L);
    scanf("%d",&temp);
    while(temp != -1){
        p=(LinkList) malloc (sizeof(LNode));
        p->data = temp;
        p->next=NULL;
        r->next =p;
        r=p;
        scanf("%d",&temp);
    }
}
LNode* getElme(LinkList L,int i){
    int j=1;
    LinkList p = L->next;
    if(i<0) return NULL;
    if(i==0) return L;
    while(p&&j<i){
        p=p->next;
        j++;
    }
    return p;
}
void showList(LinkList L){
    LinkList temp = L->next;
    while(temp!= NULL){
        printf("%d ",temp->data);
        temp = temp->next;
    }
}
void deleteNode(LNode* head,LNode* _delete){
    //异常情况
    if(head==NULL || _delete==NULL) return;
    //一般情况 _delete 位于中间部分
    if(_delete->next!=NULL){
        LNode* temp= _delete->next;
        _delete->data=temp->data;
        _delete->next=temp->next;
        free(temp);
    }else{  //特殊情况，_delete是最后一个结点
        LNode* temp;
        for(temp=head;temp->next!=_delete;temp=temp->next);
        temp->next=NULL;
        free(_delete);
    }
}
void main(){
    LinkList L;
    //输入 1 2 3 4 5 6 -1
    createList_tail(&L);
    //获取第二个元素 2
    LNode* _delete=getElme(L,2);
    //删除第二个元素 2
    deleteNode(L,_delete);
    //获取第后一个元素 6
    _delete=getElme(L,5);
    //删除最后一个元素 6
    deleteNode(L,_delete);
    showList(L);
}