关于单链表逆序输出的问题，如果不用递归的话，怎么解决，自己写了段代码，一运行就崩溃。求大神赐教。
发布网友
发布时间：2022-08-16 00:58
共3个回答
热心网友
时间：2023-09-25 10:48
比如链表是：
head -> n1 -> NULL
下面没步骤执行的时候：
while(L->next!=NULL)
{
p=L->next; //执行到这一步的时候， p = n1;
while(p->next!=NULL) //这个循环不会执行，因为 p->next 现在已经是null了。注意q没有赋值
{
q=p;
p=q->next;
}
cout<<p->data<<" "; //这步会正确打印n1中的数字；
q->next=NULL; //这步挂了。看到了吗？q还没有赋值！！！
free(p);
}
}
代码改成：
void PrintInverted(LNode *&L)
{
LNode *p,*q;
while(L->next!=NULL)
{
q = L; //就加这一行就行了！！！！！！！！！！！
p=L->next;
while(p->next!=NULL)//找到终结点
{
q=p;
p=q->next;
}
cout<<p->data<<" ";
q->next=NULL;
free(p);//删除最后一个结点
}
}
另外，既然是打印完了之后链表就销毁了，其实还有一种时间复杂度更高的方法：
1、先遍历到链表的末尾，遍历的时候，直接把链表逆序；
2、然后依次删除链表就行了。
就像我代码里面些的，从你的实现上，函数传入的头指针L里面应该是没有装数据的，我下面的代码是按照这个来写的。如果L面是有数据，行数会更短，稍微改下就可以了，你懂的。
代码如下：
void PrintInverted(LNode *&L)
{
LNode* p, *q, *r;
//L 是头指针（从你实现上，这个应该是没有装数据的，这个不动)。
//剩下的逆序
p = L->next;
if(p == NULL)
{//此时链表为空，没有数据;
return;
}
q = p->next;
p->next = NULL;
while(q != NULL)
{
r = q;
q = q->next;
r -> next = p;
p = r;
}
//此时，链表已经逆序，装有数据的表头为p，然后是“顺序”打印，你懂的
while( p != NULL)
{
cout<<p->data<<" ";
q = p;
p = p->next;
free(q);
}
}
热心网友
时间：2023-09-25 10:48
{
LNode *p=L->next,*q=L; //这里给初值
if ( p!=NULL) //如果是空表则不处理
{
while(p->next!=NULL)//找到终结点
{
q=p;
p=q->next;
}
cout<<p->data<<" ";
q->next=NULL;
free(p);//删除最后一个结点
}
}
热心网友
时间：2023-09-25 10:48
这是个例子
*/
# include "stdio.h"
# include "stdlib.h"
typedef struct LNode
{
char data;
LNode * next;
} * LinkList;
LinkList create_list(char * A);
void traverse_list(LinkList pHead);
LinkList PrintInverted(LinkList L);
int main(void)
{
char * A = "abcdefg";
LinkList pHead;
pHead = create_list(A);
printf("遍历单链表中的元素:");
traverse_list(pHead);
PrintInverted(pHead);
printf("元素倒置后，遍历单链表:");
traverse_list(pHead);
return 0;
}
LinkList create_list(char * A)
{
int len;
int i;
int val;
LinkList pHead = (LinkList)malloc(sizeof(LNode));
LinkList pTail = pHead;
pTail->next = NULL;
for (i=0;i<7;++i)
{
LinkList pNew = (LinkList)malloc(sizeof(LNode));
pNew->data = A[i];
pTail->next = pNew;
pNew->next = NULL;
pTail = pNew;
}
return pHead;
}
void traverse_list(LinkList pHead)
{
LinkList p = pHead->next ;
while (NULL != p)
{
printf("%c ",p->data);
p = p->next;
}
printf("\n");
return ;
}
LinkList PrintInverted(LinkList L)//单链表的倒置算法
{
LNode * p,* q;
p = L->next;
L->next = NULL;
while(p)
{
q = p;
p = p->next;
q->next = L->next;
L->next = q;
}
return L;
}
/*
结果：
------------------------
遍历单链表中的元素:a b c d e f g
元素倒置后，遍历单链表:g f e d c b a
Press any key to continue
------------------------------
*/
