请选择 进入手机版 | 继续访问电脑版

2021-01-01

[复制链接]
菜鸡 发表于 2021-1-2 19:44:38 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
有趣的算法——从无头链表中删除节点

最近看《编程之美》,内里有许多有趣的算法,此中这个是我没想到的,给了我很大启发。这里分享一下。
题目是这样的:给一个无头单链表,一个指针指向某个节点,要将他删掉。
…->A->B->C->D->…,pCurrent指针指向B,要求删掉B,变成…->A->C->D->…
正常的做法是找到这个给定节点的前序节点,然后做指针使用让A直接指向C,释放掉B,但是很显然现在无法遍历找到前序节点A。
答案告诉我不要拘泥于是否删掉 “某个特定节点”,显然强行删不掉B,只要最终效果是ACD就行了,那么就把B变成C,然后删掉原来的C就行了。学到了,开阔思维了。
解法如图:
…->A->B->C->D->…
…->A->C->C->D->…
…->A->C->D->…
  1. void deleteNode (node* pCurrent) {        if(pCurrent->next == NULL) {                free(pCurrent);        } else {                node* pNext = pCurrent->next;                pCurrent->data = pNext->data; // 狸猫换太子,把C的值给B                pCurrent->next = pNext->next; // 原来的C成替死鬼被删掉了                free(pNext);        }}
复制代码
这个题目告诉我,不要要求删哪个节点就删哪个节点,只要得到最后的效果,我管你删的是哪个节点。
扩展题目

编写一个函数,给定一个链表的头指针,要求只遍历一次,将单链表中的元素顺序反转过来。
第一个想法就是用栈,从FIFO到FILO刚好反转过来,出栈尾插法构建新的链表,然反面指针指向新链表的表头就行。
大概遍历的时候头插法创建新的链表,把原链表的头指针暂存,最后再指向新链表的头节点就行。

来源:https://blog.csdn.net/Hoitsuhan/article/details/112058463
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )