单链表倒置算法

㈠ 单链表的就地逆置的算法！！

就地逆置即算法的辅助空间为O(1)。

思路为：逆置链表初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。

实现代码：

voidconverse(LinkList*head)
{
LinkList*p,*q;
p=head->next;
head->next=NULL;
while(p)
{
/*向后挪动一个位置*/
q=p;
p=p->next;

/*头插*/
q->next=head->next;
head->next=q;
}
}

㈡ 单链表的逆置算法

帮你写好了，你看下

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
int data;
struct node *next;
}Node;

//创建链表
Node *CreatList(void)
{
int i;
Node *head, *p, *q;

head = NULL;
printf("请输入您要输入的数据:\n");
scanf("%d", &i);
while(i != 0)
{
p = (Node *)malloc(sizeof(Node));
p->data = i;
if(head == NULL)
q = head = p;
else
q->next = p;
q = p;
scanf("%d", &i);
}
p->next = NULL;
return head;
}

//链表的逆置
Node *ReverseList(Node *head)
{
Node *p, *q, *r;

p = head;
q=r=NULL;

while(p)
{
q = p->next;
p->next = r;
r = p;
p = q;
}
return r;
}

//输出链表
void PrintList(Node *head)
{
Node *p;

p = head;
while(p)
{
printf("%d\n", p->data);
p = p->next;
}
}

int main(void)
{
Node *head;

head = CreatList();
printf("链表逆置前的数据:\n");
PrintList(head);

head = ReverseList(head);
printf("链表逆置后的数据:\n");
PrintList(head);

return 0;
}

请输入您要输入的数据:
1 2 3 4 5 6 0
链表逆置前的数据:
1
2
3
4
5
6
链表逆置后的数据:
6
5
4
3
2
1