首页 > 代码库 > 链表 2.3
链表 2.3
实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。
示例
输入：单向链表a->b->c->d->e中的结点c。
结果：不返回任何数据，但该链表变为：a->b->d->e。
分析：因为无法访问待删除结点的前继结点，所以只能通过复制将后续链表整体向前移动一个位置，并删除最后一个多余的结点。显然，当待删除结点为链表的尾结点时（即没有后继），该问题无解。
1 #include <iostream> 2 #include <fstream> 3 #include <assert.h> 4 5 using namespace std; 6 7 struct Node { 8 Node(): val(0), next(0) {} 9 Node( int value ): val(value), next(0) {}10 int val;11 Node *next;12 };13 14 void removeNode( Node *node );15 16 int main( int argc, char *argv[] ) {17 string data_file = "./data.txt";18 ifstream ifile( data_file.c_str(), ios::in );19 if( !ifile.is_open() ) {20 fprintf( stderr, "cannot open file: %s\n", data_file.c_str() );21 return -1;22 }23 int n = 0, k = -1;24 while( ifile >>n >>k ) {25 assert( n > 0 && k > 0 && k < n );26 Node guard, *node = &guard, *target = 0;27 for( int i = 0; i < n; ++i ) {28 node->next = new Node();29 node = node->next;30 ifile >>node->val;31 cout <<node->val <<" ";32 if( i == k-1 ) { target = node; }33 }34 cout <<endl;35 if( target ) 36 cout <<"target to remove: " <<target->val <<endl;37 else38 cout <<"target to remove: null" <<endl;39 removeNode( target );40 node = guard.next;41 cout <<"result:" <<endl;42 while( node ) {43 Node *next = node->next;44 cout <<node->val <<" ";45 delete node;46 node = next;47 }48 cout <<endl <<endl;49 }50 ifile.close();51 return 0;52 }53 54 void removeNode( Node *node ) {55 assert( node && node->next );56 node->val = node->next->val;57 while( node->next->next ) {58 node = node->next;59 node->val = node->next->val;60 }61 delete node->next;62 node->next = 0;63 return;64 }
测试文件
2 11 33 11 2 33 21 2 37 114 54 96 23 45 12 457 214 54 96 23 45 12 457 614 54 96 23 45 12 45
链表 2.3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。