首页 > 代码库 > careercup-链表 2.3

careercup-链表 2.3

2.3 实现一个算法,删除单向链表中间的某个结点,假设你只能访问该结点。(即你不知道头结点)

这个问题的关键是你只有一个指向要删除结点的指针,如果直接删除它,这条链表就断了。 但你又没办法得到该结点之前结点的指针,是的,它连头结点也不提供。在这种情况下, 你只能另觅他径。重新审视一下这个问题,我们只能获得从c结点开始后的指针, 如果让你删除c结点后的某个结点,那肯定是没问题的。比如删除结点d,那只需要把c 的next指针指向e,然后delete d就ok了。好的,如果我们就删除结点d,我们将得到 a->b->c->e,和目标链表只差了一个结点。怎么办呢?把d的数据给c! 结点结构都是一样的,删除谁都一样,最关键的是结点中的数据,只要我们留下的是数据 a->b->d->e就OK了

思路已经有了,直接写代码?等等,写代码之前,让我们再简单分析一 下可能出现的各种情况(当然包括边界情况)。如果c指向链表的:1.头结点;2.中间结点。 3.尾结点。4.为空。情况1,2属于正常情况,直接将d的数据给c,c的next指针指向d 的next指向所指结点,删除d就OK。情况4为空,直接返回。情况3比较特殊,如果c 指向尾结点,一般会认为直接删除c就ok了,反正c后面也没有结点了,不用担心链表断开。 可是真的是这样吗?代码告诉我们,直接删除c,指向c的那个结点(比如说b)的next指针 并不会为空。也就是说,如果你打印这个链表,它还是会打印出和原来链表长度一样的链表, 而且最后一个元素为0

 

关于这一点,原书CTCI中是这么讲的,这正是面试官希望你指出来的。然后, 你可以做一些特殊处理,比如当c是尾结点时,将它的数据设置为一些特殊字符, 这样在打印时就可以不打印它。当然也可以直接不处理这种情况,原书里的代码就是这么做 的。这里,也直接不处理这种情况。

  C++实现代码:

#include<iostream>#include<new>using namespace std;struct ListNode{    int val;    ListNode *next;    ListNode(int x):val(x),next(NULL) {}};void createList(ListNode *&L){    int arr[10]= {1,2,3,2,5,6,7,3,9,1};    int i;    ListNode *p=NULL;    for(i=0; i<10; i++)    {        ListNode *tmp=new ListNode(arr[i]);        if(L==NULL)        {            L=tmp;            p=tmp;        }        else        {            p->next=tmp;            p=tmp;        }    }}void deleteNode(ListNode *c){    if(c==NULL||c->next==NULL)        return;    ListNode *d=c->next;    c->next=d->next;    c->val=d->val;    d->next=NULL;    delete(d);}int main(){    ListNode *head=NULL;    createList(head);    ListNode *p=head;    while(p)    {        cout<<p->val<<" ";        p=p->next;    }    cout<<endl;    deleteNode(head->next->next->next);    p=head;        while(p)    {        cout<<p->val<<" ";        p=p->next;    }    cout<<endl;}

 

careercup-链表 2.3