求各位帮忙看看这个单链表就地反转的反转哪里错了

来源：蜘蛛抓取(WebSpider) 时间：2020-04-16 12:43 标签： 单链表就地反转

就地反转即不能创建新的节点；

思路：反转一个链表，需要调整链表指针；
i,m,n 3个连续的节点此时i之前的指针已经调整好了，当前的节点为mpre=i，在调整m的指针之前需要先记录下m的下一个指针n，然后再调整；


这道题我的思路就是：将那个降序的链表反转后用上一题的代码，来将它们合并成一个降序的序列

把当前链表的下一个节点pCur插入到头结点dummy的下一个节点中就地反转。

?方法2：新建链表头节点插入法

新建一个头结点，遍历原链表把每个节点用头结点插入到新建链表中。
最后新建的链表就是反转后的鏈表。

//这个程序的问题 l1只可以是增序l2只可以是降序 //否则的话merge这个函数要修改 //merge函数用的是上一道题的代码 //有空的时候来修改一下merge函数 //一个昰升序 一个是降序 将其合并为一个有序的链表 //我想的方法是反转一个 然后再比较 （单链表就地反转的反转一般有两种，我选择的是原地反轉） //我这里依旧选择原地合并 //这里我偷懒用了上一题的代码所以顺序是倒着的，反正题目只要求了有序

链表反转问题当然可以通过重新建表这样做简单明了，但空间复杂度是O(n)为了更优，一般要求就地反转即要求空间复杂度为O(1)。

（1）第一种实现思路是：因为头插法建表是逆序的可以在遍历链表的同时，边逐个摘出节点边逐个插入头节点后面（头插法），这样就不需要有辅助空间了

（2）第二种实現思路是：因为只有一个节点的链表既是正序的又是逆序的，即规模为1时已有解

那么可以把前面已经逆序的那段链表A看做一个整体，然後A与A的下一个节点B交换位置就可以形成规模加1的反转链表A 

为使思路清晰，首先要知道链表操作的实质即前驱节点的指针决定了其后继節点是谁。

要交换A意味着要知道A的前驱节点，所以设A的开始指针为headA的结束指针为head->next（指向A链表的最后一个元素）。

不难推断当且仅当A鏈表的规模==原链表规模时，即结束指针end->next == NULL时原链表的就地反转完毕。

交换过程可以画图辅助分析

首先保存指向B的指针，然后A的后继节点設为B的后续节点再将B的后继节点指向A链表的第一个有效元素(begin->next)，此时A链表表头应指向B

即A的前驱节点的next不再指向原来的A链表，而是指向B节點此时A和B的后续都已正确设置完毕。

我要回帖

更多关于 单链表就地反转 的文章

 

随机推荐