/*
问题描述，如何在时间复杂度为O(n)的前提下，实现单链表翻转。
并尽量减少内存消耗。
即1-2-4-5-6转化为6-5-4-2-1。
*/
1 # include<stdio.h>
4 struct Slist{
5
6 int size;
7 struct sl* head;
8
9
10 };
11 struct sl{
12
13 int k;
14 struct sl* next;
15
16
17 };
18 typedef struct Slist Sl;
19 typedef struct sl sl;
20
21
22 void init(Sl* m,int k){
23
24 sl* p = (sl *)malloc(sizeof(sl));
25 p->k = k;
26 p->next = NULL;
27 m->head =p;
28 m->size = 1;
29 //printf("%x, %d, %x", m->head,m->size,p);
30 }
31
32 void add(Sl* m,int key ){
33 //printf("%x", m->head);
34 sl* p=(sl *)malloc(sizeof(sl));
35 sl* q = (sl *)malloc(sizeof(sl));
36 p->k = key;
37 p->next = NULL;
38 q = m->head;
39 while (q->next != NULL)
40 q = q->next;
41 q->next = p;
42 m->size++;
43 }
44
45 void FanZhuan(Sl* m){
46
47 sl* p = m->head;
48 sl* q =NULL;
49 sl* r =NULL;
50 while (p->next!=NULL){ //三指针循环记录转换，单次扫描，修改链表元素指针。
51
52 q = p->next;
53 p->next = r;
54 r = p;
55 p = q;
56 } //此时，最后一个元素的指针还没修改完成。57 q->next = r;
58 m->head = q; //链表完成后，记得把链表头修改为原链表尾地址。
59 }
60
61
62 void BianLi(Sl* m){
63
64 sl* a = m->head;
65 printf("
");
66 while (a != NULL){
67 printf("%d",a->k);
68 a = a->next;
69 }
70 }
71
72 void main(){
73
74
75 Sl* t = (Sl*)malloc(sizeof(Sl));
76 t->size=0;
77 t->head = NULL;
78 init(t,8);
79 add(t, 3);
80 add(t, 2);
81 add(t, 1);
82 add(t, 0);
83 printf("
The new list:
");
84 BianLi(t);
85 FanZhuan(t);
86 printf(" nThe list turned:
");
87 BianLi(t);
88 system("pause");
89 }