设计一个算法将带头结点的单链表逆置?

Question

这里没说是动态单链表哦！！

Answer 1

链表反序，设有数据结构
typedef struct _list_node
{ double keyVal;
struct _list_node *next;
}ListNode;

ListNode* reverseList(ListNode* head)
{
ListNode *p1, *p2 , *p3;
//链表为空，或是单结点链表直接返回头结点
if (head == NULL || head->next == NULL)
{
return head;
}
p1 = head;
p2 = head->next;
while (p2 != NULL)
{
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
head->next = NULL;
head = p1;

return head;
}

Answer 2

算法(头结点为L)
p=L->next;
q=p->next;
r=q->next;
p->next=NULL;
while(r)
{
q->next=p;
p=q;
q=r;
r=r->next;
}
L->next=q;
q->next=p;
-------------------------C程序如下
/*链表逆置*/
#define NULL 0
typedef int DataType;
typedef struct node{
DataType data;
struct node *next;
}LinkedNode,*LinkList;

main()
{
LinkList L,p,q;
DataType d;
void change(LinkList L);/*逆置单链表*/
void print(LinkList L);/*格式化输出*/

/*链表初始化*/
L=(LinkedNode *)malloc(sizeof(LinkedNode));
L->next=NULL;
p=L;
while(1)
{
printf("Input data(End of 0):");
scanf("%d",&d);
if(d==0)break;
if((q=(LinkedNode *)malloc(sizeof(LinkedNode)))==NULL)
{
printf("ERROR!");
getch();
exit(0);
}
q->data=d;
q->next=NULL;
p->next=q;
p=q;
}
/*初始化结束*/
printf("Before change:\n");
print(L);
printf("\nAfter change:\n");
change(L);
print(L);
getch();
}

/*逆置单链表*/
void change(LinkList L)
{
LinkList p,q,r;
p=L->next;
q=p->next;
r=q->next;
p->next=NULL;
while(r)
{
q->next=p;
p=q;
q=r;
r=r->next;
}
L->next=q;
q->next=p;
}
/*格式化输出*/
void print(LinkList L)
{
LinkList p=L;
if(p->next)
while(p->next)
{p=p->next;
printf("%d - ",p->data);
}
}

Answer 3

把原来是动态单链表的改了一下

用头插入法来做，直到输入0时，按enter键结束。

#include <iostream>
using namespace std;
typedef struct lnode
{
int data;
struct lnode *next;
}Lnode,*Linklist;
Linklist Creat_linklist()
{
Linklist L=NULL;
Lnode *s;
int x;
cin>>x;
while(x!=0)
{
s=new Lnode;
s->data=x;
s->next=L;
L=s;
cin>>x;
}
return L;

}
int main()
{

cout<<"请输入数据："<<endl;
Linklist p;
p=Creat_linklist();

while(p!=NULL)
{
cout<<p->data<<' ';
p=p->next;
}

return 0;
}