首页 > 代码库 > 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。