2 qq 33963483 qq_33963483 于 2016.03.17 14:17 提问

单链表的就地逆置 辅助空间为O(1)

求大神给个单链表的就地逆置 要不开拓辅助空间 原谅我没有C币

2个回答

cxsmarkchan
cxsmarkchan   2016.03.17 15:20
已采纳
struct Node{
    int value;
    Node *next;
};
void reverse(Node* head){
    Node *prev, *cur, *next;
    cur = head;
    prev = NULL;
    while(cur != NULL){
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
}
cxsmarkchan
cxsmarkchan 回复qq_33963483: 你可以自己画一个小的链表,然后模拟while循环中的每一步时,prev, cur, next都分别指向什么。模拟几步应该就能明白了。
2 年多之前 回复
cxsmarkchan
cxsmarkchan 回复qq_33963483: 这段代码的重点在于:你在改变cur的next指向时,一方面要知道cur的上一个对象是什么,所以需要prev来存;另一方面需要保存cur的下一个对象,不然改变了cur->next值之后,原来cur指向的元素就找不到了,所以要用一个next来暂存下一个对象。
2 年多之前 回复
qq_33963483
qq_33963483 可以帮我解释一下吗 还是有一点不懂
2 年多之前 回复
qq_33963483
qq_33963483   2016.03.17 18:55

可以帮我解释一下吗 还是有点不理解

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
第1章第2节练习题11 就地逆置单链表
试编写在带头结点的单链表就地逆置,所谓“就地”是指辅助空间为O(1)
将链表L就地逆置,即利用原表各结点的空间实现逆置
一、题目将链表L就地逆置,即利用原表各结点的空间实现逆置。二、思路在链表的第二个元素开始执行逆置,因为如果链表只有一个元素,那么逆置就没有意义了。步骤: 假设原链表如下: 将结点1的指针指向结点3,也就是说将结点2脱离链表: 然后将L链表的头结点指针指向结点2,然后结点2变成第一个元素,结点2的指针指向结点1,此刻实现了第一个逆置。 重复上述2、 3步,将结点3脱离链表,然后就可以接到头结点
【学习点滴-数据结构-单链表】单链表的就地逆置
题目描述:给定一个单链表,对此单链表进行就地逆置 “就地”:是指不需要开辟新的链表空间,而是在原链表的基础上调整指针的走向/*  * 算法功能:建立单链表,对单链表进行就地逆置。  * 算法中的单链表是不带头结点的。   * 函数说明:  * 1.TransLinklist(Linklist &L):递归地对单链表进行逆置  * 2.TranLinkNoneRecur(Linklist
【应用】单链表的就地逆置
单链表的就地逆置时限:1000ms 内存限制:10000K 总时限:3000ms描述读入数据构造一个单链表,实现单链表的就地逆置。输入先输入一个小于100的正整数n,再从小到大的输入n个正整数,建立一个单链表,然后实现单链表的就地逆置。输出按顺序输出逆置后的单链表的所有元素,每个元素占一行。输入样例3 300 3000 50000输出样例50000 3000 利用头插法 void ListR
实现单链表的就地逆置
头文件和宏定义#include<iostream> #include<stdio.h> #include<stdlib.h> #include<malloc.h> using namespace std; #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBL
对单链表实现就地逆置算法
对以单链表为存储结构的表实现就地逆置,即在原有空间上实现逆置,不开辟新空间
C语言链表就地逆置操作
在c语言中,为了节省空间和时间,我们可以采取在原空间上实现链表的逆置每次读取一个节点时,将他用头插法的方法加入到链表中,最后得到的即是逆置后的链表了关键掌握头插法的思路:q-&amp;gt;next=l-&amp;gt;next;l-&amp;gt;next=q;下面是具体方法实现以及说明:void  PrintLinklist_back(linklist l)   { linklist pre = l-&amp;gt;next...
单链表的逆序输出及就地逆置
单链表的逆序输出: void R_Print(LinkList L){ if(L->next) R_print(L->next); print(L->data); } 单链表的就地逆置: 就地逆置即空间复杂度为O(1) 解法一: 将头结点摘下,然后从第一结点开始,依次前插入到头结点的后面(头插法建立单链表),直到最后一个结点为止 LinkList Rev
C++ 单链表的 就地逆置 ,以及基本操作
#include "stdafx.h" #define sub(a,b) a-b //没用 #include using namespace std; struct node { int a; node * next; }; int _tmain(int argc, _TCHAR* argv[]) { //int x=sub(3,8); node * createList
带头结点的单链表实现就地逆置的更优方法
在习惯上,我们在实现链表的逆置时都会采用从第一个结点开始遍历并不断将链表的指向逆置的方法,但这样做效率其实不高。假设要逆置的链表为L,更好的方法是先用指针p保存L-〉next,再将链表L的头结点置为Null,亦即L-〉next=Null,而后将p所指向的原存在于L的各个结点插入在已经置空的L中,作为L的第一个元素结点,p则每次下移用于记录剩下结点的位置。具体代码如下: p=L->next; L