單鏈表倒置演算法

㈠ 單鏈表的就地逆置的演算法！！

就地逆置即演算法的輔助空間為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