怎样就地反转单链表?

 #返回上一级

@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的后续都已正确设置完毕。

 

 #返回上一级

怎样就地反转单链表?

上一篇:为Android编译bash


下一篇:浅谈设计模式--单例模式(Singleton Pattern)