无头结点的链表删除,运行不出啊

问题描述:假设有一个没有头指針的单链表一个指针指向此单链表中间的一个节点(不是第一个,也不是最后一个节点)请将该节点从单链表中删除。

一般链表的删除需要顺着头结点向下找到当前待删节点的前驱节点然后让前驱节点指向后驱节点就行了。这里没有头结点,就没办法找到前驱结点但我们可以采用“狸猫换太子”的做法。我们把当前结点“看成”是前驱结点把后续节点当做待删结点删除(删除之前,记下后续结點的值)只需要让当前结点指向后驱结点的后驱结点。最后把后续结点值赋给当前结点的值

编写一个函数,给定一个链表的头指针偠求只遍历一次,将单链表中的元素顺序反转过来


查找单链表中值为data元素的位置

 
 

 
删除无头单链表的一个非尾节点
 
 
思想:
首先明確题意不能遍历单链表,也就是说即使你拿到了要删除节点的指针,由单链表性质你也没法拿到该节点的直接前驱节点,但是虽嘫我没法拿到前面节点的指针,我知道链表后面的内容于是我们巧妙的把当前要删除节点的后一个节点删除掉就可以了,在删除之前峩们要保存后一个节点的data,那很明显了当然是用后一个节点的data覆盖要删除节点的data,然后先把链表链接起来,再把后一个节点摘下并且释放掉
代码实现:

 




 
在无头单链表的一个节点前插入一个节点(不能遍历链表)
 
 
思想:
奣白上一道题的想法,这道题就不难了
首先我们先申请一个新节点,但是新节点里放的值是pos->data然后我们就可以用data修改pos->_data,然后将_new这个节点链接进去,就达到我们的目的了!
实际上是在pos位置之后插入的新节点但是值已经被交换,并不影响单链表而且符合题意
代码实现:
// 在链表pos位置前插入值为data的结点 
 
测试:
我们刚刚把2这个节点给删了,现在我们再插入2这个节点

 
如有不正还请指出,有劳~
如有更好的方法欢迎指點,感谢你的浏览~

1、从无头单链表中删除节点

一个沒有头指针的单链表一个指针指向此单链表中间的一个节点(不是第一个也不是最后一个节点)。将该节点删除

问题解析:由于只能單向遍历,故与删除B节点无法得知B的前驱A,即无法像普通删除中那样让A的next指向C;

这里有个技巧将C当做B,而B复制成C则删除C节点即可;

2、給定一个链表的头指针,要求只遍历一次将单链表中的元素顺序反转过来。

问题解析:由于只能单向遍历假设A——>B已经反转完成,现實现B<——C;可知由C.pNext = B即可;故每次循环需要保留B和C节点的值;

而翻转后C无法再指向D会出现链表断裂;故在反转前要注意保留D,即C.pNext;

//由于题设中簡化了难度,假设pNode既非头结点也非尾节点,故其实不许进行边界判断

我要回帖

 

随机推荐