@Author: 张海拔
@Update: 2014-01-23
@Link: http://www.cnblogs.com/zhanghaiba/p/3531439.html
1 /* 2 *Author: ZhangHaiba 3 *Date: 2014-1-23 4 *File: single_linked_list_reverse.c 5 * 6 *a demo shows how to reverse a single_linked_list in-place 7 */ 8 9 10 #include <stdio.h> 11 #include <stdbool.h> 12 #include <stdlib.h> 13 #define INF 0x7fffffff 14 #define CMD_LNE 128 15 16 typedef struct node* link; 17 typedef struct node { 18 int item; 19 link next; 20 }node; 21 22 //public 23 link NODE(int item, link next); 24 void list_reverse1(link head); 25 void list_reverse2(link head); 26 link list_create(int n); 27 void list_travel(link head); 28 void list_destroy(link head); 29 30 int main(void) 31 { 32 int n; 33 34 scanf("%d", &n); 35 link list_a = list_create(n); 36 printf("Travel a_list: \n"); 37 list_travel(list_a); 38 list_reverse1(list_a); 39 printf("Travel a_list after reverse: \n"); 40 list_travel(list_a); 41 list_reverse2(list_a); 42 printf("Travel a_list after reverse again: \n"); 43 list_travel(list_a); 44 return 0; 45 } 46 47 //think as head insert 48 void list_reverse1(link head) 49 { 50 link p = head->next; 51 52 head->next = NULL; 53 while (p != NULL) { 54 link save = p->next; 55 p->next = head->next; 56 head->next = p; 57 p = save; 58 } 59 } 60 61 //think as swap node in-place 62 void list_reverse2(link head) 63 { 64 link begin = head; 65 link end = head->next; 66 67 while (end->next != NULL) { 68 link save = end->next; 69 end->next = save->next; 70 save->next = begin->next; 71 begin->next = save; 72 } 73 } 74 75 link NODE(int item, link next) 76 { 77 link born = malloc(sizeof (node)); 78 born->item = item; 79 born->next = next; 80 return born; 81 } 82 83 //create by ‘tail insert‘ 84 link list_create(int n) 85 { 86 int i, item; 87 link head = NODE(INF, NULL); 88 link tail = head; 89 90 for (i = 0; i < n; ++i) { 91 scanf("%d", &item); 92 tail->next = NODE(item, NULL); 93 tail = tail->next; 94 } 95 return head; 96 } 97 98 void list_travel(link head) 99 { 100 for (head = head->next; head != NULL; head = head->next) 101 printf(head->next == NULL ? "%d\n" : "%d ", head->item); 102 } 103 104 void list_destroy(link head) 105 { 106 head->next == NULL ? free(head) : list_destroy(head->next); 107 }
测试示范:
ZhangHaiba-MacBook-Pro:code apple$ ./a.out 8 43 534 423 4346 63 52336 31 5 Travel a_list: 43 534 423 4346 63 52336 31 5 Travel a_list after reverse: 5 31 52336 63 4346 423 534 43 Travel a_list after reverse again: 43 534 423 4346 63 52336 31 5
链表反转问题当然可以通过重新建表,这样做简单明了,但空间复杂度是O(n),为了更优,一般要求就地反转,即要求空间复杂度为O(1)。
这里给出两种实现
(1)第一种实现思路是:因为头插法建表是逆序的,可以在遍历链表的同时,边逐个摘出节点,边逐个插入头节点后面(头插法),这样就不需要有辅助空间了。
首先设p指向第一个有效节点(p = head->next),再分离出头节点,即设头结点下一个节点为空(head->next = NULL)。
为了能成功遍历,先保存p的next指针即save = p->next,然后头插:p->next = head->next,head->next = p,最后p = save得以继续遍历后面的链表。
(2)第二种实现思路是:因为只有一个节点的链表既是正序的又是逆序的,即规模为1时已有解。
那么可以把前面已经逆序的那段链表A看做一个整体,然后A与A的下一个节点B交换位置就可以形成规模加1的反转链表A。
为使思路清晰,首先要知道链表操作的实质,即前驱节点的指针决定了其后继节点是谁。
要交换A,意味着要知道A的前驱节点,所以设A的开始指针为head,A的结束指针为head->next(指向A链表的最后一个元素)。
不难推断,当且仅当A链表的规模==原链表规模时,即结束指针end->next == NULL时,原链表的就地反转完毕。
交换过程可以画图辅助分析。
link save = end->next,end->next = save->next, save->next = begin->next; begin->next = save;
首先保存指向B的指针,然后A的后继节点设为B的后续节点,再将B的后继节点指向A链表的第一个有效元素(begin->next),此时A链表表头应指向B,
即A的前驱节点的next不再指向原来的A链表,而是指向B节点,此时A和B的后续都已正确设置完毕。