单链表的反向

为了方便解释，将链表长度设为了5。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 //链表定义
 5 typedef struct node{
 6     int data;
 7     struct node *next;
 8 }link;
 9 
10 //构造链表
11 link * create_link(link *head)
12 {
13     int data[5];
14     int i=0;
15     while(i<5)
16     {
17         scanf("%d",&data[i]);
18         i++;
19     }
20     link *p=head;//p为每次链表更新后的最后一个节点
21     for (i=0;i<5;i++)
22     {
23         link *q=(link*)malloc(sizeof(link));
24         q->data=data[i];
25         q->next=NULL;
26         p->next=q;
27         p=q;
28     }
29     return head;
30 }
31 
32 //链表反向
33 link * reserve_link(link *head)
34 {
35     link *last=head->next;//last为链表最后一个节点，反向后为第一个节点
36     int num=1;
37     while (last->next!=NULL)
38     {
39         num++;
40         last=last->next;
41     }
42     link *p,*q;//p为链表更新后反向那端开始的最后一个节点
43     p=last;
44     int i;
45     for (i=num-1;i>=1;i--)
46     {
47         int j=1;
48         q=head->next;
49         while (j<i)//找出原向的第i各节点p
50         {
51             q=q->next;
52             j++;
53         }
54         p->next=q;
55         q->next=NULL;//此时节点q的next域是空，不加此句最后的两个节点会成环
56         p=q;
57     }
58     head->next=last;
59     return head;
60 }
61 
62 int main()
63 {
64     link *head=(link*)malloc(sizeof(link));
65     head->data=0;
66     head->next=NULL;
67 
68     link *li=create_link(head);
69 
70     link *relink=reserve_link(head);
71 
72     return 0;
73 }

声明测试环境是vc6.0，在70行和72行分别加两个断点，测试结果如下：

原先链表：

反向后的链表：