给定一个单链表，编程实现其逆转。单链表的逆转过程的关键是3个指针：一个记录当前逆转节点的前一个节点，一个记录当前逆转节点的下一个节点，另外一个则记录当前的逆转节点。为什么要3个指针呢？其原因就在于当修改了当前逆转节点的next域后（逆转），链表就暂时断了（即无法再定位下一个节点），因此需要一个指针记录其下一个节点位置（要能够依次遍历）。记录前一个节点位置则很明显：因为要将当前逆转节点的next域指向其上一个节点（这样才叫逆转）。
//逆转单链表
struct node *reverse_LList(node *head)
//以p作为当前结点处理,头结点为逆转前的头结点
struct node *p,*q,*
if(head == NULL)
cout && "空表" &&//头结点为0,空表
//q指向头结点
p = head-&
//p指向头结点后一个结点
//头结点进一位
temp = p-&
//保存当前结点指针域
q-&next = NULL;
//逆转头结点为尾结点的情况,头指针为空
//后一个结点指向头结点
while(temp-&next != NULL) //判断当前结点的后一结点指针域是否为空,即判断是否为尾结点
//q指向头结点
//p指向头结点后一个结点
temp = p-& //保存当前结点指针域
//头结点进一位
//后一个结点指向头结点
//此时temp表示以前的尾结点,p表示temp结点的前一结点
//逆转尾结点为头结点
head-&next = //头结点指针域指向p
Node* LinkListReserve(LinkNode head)
LinkNode p = NULL; //记录逆转节点的前一个节点；
LinkNode r = //记录当前节点;
LinkNode q = NULL; //记录逆转节点的下一个节点；
while (r != NULL)
//保存下一个节点
r-&_next =
//下一次遍历
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：4698次
排名：千里之外
原创：12篇问题补充&&
感觉第二种逻辑要简单些
李小冬天的&2-26 15:00
猜你感兴趣
信息来源于互联网，不保证内容的可靠性、真实性及准确性，仅供参考，版权归原作者所有！Copyright &
Powered by编写一个带头结点的单链表就地逆置（不允许构建新的链表，只能在原_数据结构吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：17,379贴子：
编写一个带头结点的单链表就地逆置（不允许构建新的链表，只能在原收藏
void&inverse(linklist*&head){&
if&(head→next==NULL）&return&;&
linklist*q=head→&
*p=q→&
*r=NULL;&
while(p!=NULL)&
{&q→next=r;&
r=q;q=p;p=p→&
}&
q→next=r;head→next=q;&
}
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或输入您需解决的
软件开发问题并开始搜索，
IT异常查询网可以方便地提供各类
程序错误解决方案。
面试题：用一个暂时变量实现单链表逆序 - 编程
&&&发布于： 21:54:54&&&
面试题：用一个临时变量实现单链表逆序通常实现某种算法有两种常用的思想：循环和递归，这两种方式都需要占用一定的空间，但是循环使用的是某一个栈帧的空间，而递归则会使运行时函数调用不断压栈导致栈帧数量的增加。我在之前的动态规划算法学习中提到的爬楼梯问题所采用的两种方式可以很好地解释这两种思想。
在《编程之美》3.4扩展问题实现中，使用循环的思想实现了链表的逆序，这种方式需要使用三个临时变量。那如何只使用一个临时变量实现单链表逆置呢？我们可以采用栈，将链表节点保存在栈结构中，但是这样也不符合只是用一个临时变量的要求。对比循环和递归的特点，对于变量个数要求的问题，递归可以很好地解决。
typedef struct Node
struct Node *
/* head是逆序后的头结点 */
Node *reverse(Node *p)
if(p == NULL || p-&pnext == NULL)
reverse(p-&pnext)-&pnext =
p-&pnext = NULL;
相关解决方法
你也许会喜欢
Web前端&&热门解决方法
Web前端&&最新解决方法
Web前端&&随机解决方法
诚心交换友情链接:qq:}