就地逆置就是将动态数组中的所有元素逆置,空间复杂度为O(1)。

它可以说是线性表最重要的应用了,下面用多种方法分别实现顺序表和单链表的就地逆置。

顺序表的就地逆置

回顾顺序表的定义:

1
2
3
4
5
6
typedef int ElemType;
typedef struct SeqList{
ElemType * elem;
int length;
int size;
}SeqList,ListPtr;

1. 设置中间量

1
2
3
4
5
6
7
8
void SeqListReverse_1(SeqList * list){
ElemType temp;
for(int i=0;i<(list->length)/2;i++){
temp=list->elem[i];
list->elem[i]=list->elem[list->length-i-1];
list->elem[list->length-i-1]=temp;
}
}

2. 使用地址指针

两端均设置一个指针,两指针逐渐向中间靠拢,指针交错时停止交换。

1
2
3
4
5
6
7
8
9
10
11
void SeqListReverse_2(SeqList * list){
ElemType * p=&(list->elem[0]);
ElemType * q=&(list->elem[list->length-1]);
while(p<q){
*p+=*q;
*q=*p-*q;
*p-=*q;
p++;
q--;
}
}

要注意上面指针的操作,有点炫技,但是可读性不高。不过这个方法还是值得学习。

1
2
3
*p+=*q;
*q=*p-*q;
*p-=*q;

与设置中间量的方法进行比较,第一种方法循环中涉及3次赋值操作、4次加减运算、4次间接寻址、4次直接寻址;第二种方法涉及3次赋值操作、3次加减运算、7次间接寻址。但是第二种方法多定义了一个指针变量。对于不同大小的ElemType,两种方法孰优孰劣还不好说。

但是,我们可以改进第二种方法,将间接寻址变为加减运算加直接寻址,即第三种方法,这样按理说效率会更高。

3. 设置计数器指针

1
2
3
4
5
6
7
8
9
10
void SeqListReverse_3(SeqList * list){
int i=0,j=list->length-1;
while(i<j){
list->elem[i]+=list->elem[j];
list->elem[j]=list->elem[i]-list->elem[j];
list->elem[i]-=list->elem[j];
i++;
j--;
}
}

很显然,上面的想法失败了。第三种方法虽然将间接寻址变成了直接寻址,但是又引入了list->的间接寻址,可以说是得不偿失。

但是,多亏了编译器在编译时将间接寻址转化为直接寻址,上面三种方法差别不大。

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10

typedef int ElemType;
typedef struct SeqList{
ElemType * elem;
int length;
int size;
}SeqList,ListPtr;

void InitSeqList(SeqList * list);
void SeqListReverse_1(SeqList * list);
void SeqListReverse_2(SeqList * list);
void SeqListReverse_3(SeqList * list);
void ListDisplay(SeqList * list);

int main(){
SeqList list;
InitSeqList(&list);
for(int i=0;i<list.size;i++){
list.elem[i]=i;
list.length++;
}
printf("原始的序列:");
ListDisplay(&list);

SeqListReverse_1(&list);
printf("交换第一次后的序列:");
ListDisplay(&list);

SeqListReverse_2(&list);
printf("交换第二次后的序列:");
ListDisplay(&list);

SeqListReverse_3(&list);
printf("交换第三次后的序列:");
ListDisplay(&list);

return 0;
}

void InitSeqList(SeqList * list){
list->elem=(ElemType*)malloc(list->size*sizeof(ElemType));
if(list->elem==NULL)
exit(0);
list->length=0;
list->size=MAXSIZE;
}
void SeqListReverse_1(SeqList * list){
ElemType temp;
for(int i=0;i<(list->length)/2;i++){
temp=list->elem[i];
list->elem[i]=list->elem[list->length-i-1];
list->elem[list->length-i-1]=temp;
}
}
void SeqListReverse_2(SeqList * list){
ElemType * p=&(list->elem[0]);
ElemType * q=&(list->elem[list->length-1]);
while(p<q){
*p+=*q;
*q=*p-*q;
*p-=*q;
p++;
q--;
}
}
void SeqListReverse_3(SeqList * list){
int i=0,j=list->length-1;
while(i<j){
list->elem[i]+=list->elem[j];
list->elem[j]=list->elem[i]-list->elem[j];
list->elem[i]-=list->elem[j];
i++;
j--;
}
}
void ListDisplay(SeqList * list){
for(int i=0;i<list->length;i++){
printf("%d",list->elem[i]);
}
printf("\n");
}

output:

1
2
3
4
原始的序列:0123456789
交换第一次后的序列:9876543210
交换第二次后的序列:0123456789
交换第三次后的序列:9876543210

单链表的就地逆置

回顾单链表节点的定义:

1
2
3
4
5
typedef int DataType;
typedef struct LinkListNode{
DataType data;
struct LinkListNode * next;
}LinkListNode,*ListPtr;

下面的单链表默认带上头节点(递归法除外)。为了避免使用二重指针,下面的函数都通过返回值进行参数传递。

1.迭代法

迭代法的原理就是一个一个地将单链表的指针反向。

实现这算法需要设置三个指针precurnex,三个指针每次都向后移动,每次移动改变一个指针的方向。

1
2
3
4
5
6
7
8
9
10
11
12
LinkListNode * LinkListReverse_1(LinkListNode * head){
LinkListNode * cur=head->next;
LinkListNode * pre=NULL, * nex=NULL;
while(cur!=NULL){
nex=cur->next;
cur->next=pre;
pre=cur;
cur=nex;
}
head->next=pre;
return head;
}

要注意这里改变的是precur之间的指针,而不能改变curnex之间的指针。

2. 递归法

递归的优点是使程序看起来优美,简单(实际上并不是表面上那么简单)。

递归法反转链表更适用于不带头结点的单链表。如果带上头结点,则需要做很多修改(反正我加了很多代码才可以),与递归的宗旨相违背。所以仅递归反转不带头结点的单链表。

1
2
3
4
5
6
7
LinkListNode * LinkListReverse_2(LinkListNode * head){
if(head==NULL||head->next==NULL) return head;
LinkListNode * tail=LinkListReverse_2(head->next);
head->next->next=head;
head->next=NULL;
return tail;
}

递归法确实有点难以理解,我也不太说得清楚。不过关键是不要按照程序运行的逻辑去想它是怎么递归的,脑袋中的栈会被压爆的。正确的做法是跳出递归,从结束递归的出口开始,往回想,然后就会发现规律。

具体的参考下面这篇文章:步步拆解:如何递归地反转链表的一部分 - 反转链表 II - 力扣(LeetCode)

3. 头插法

头插法需要需要先定义一个空串,然后把原来的链表的首元结点摘下来,最后把摘下来的结点插入新串的头节点和原首元结点之间。重复此操作,直到旧串为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
LinkListNode * LinkListReverse_3(LinkListNode * head){
if(head->next==NULL||head->next->next==NULL) return head;
LinkListNode * list=(LinkListNode*)malloc(sizeof(LinkListNode));
list->next=NULL;
LinkListNode * temp;
while(head->next!=NULL){
temp=head->next;
head->next=temp->next;
temp->next=list->next;
list->next=temp;
}
return list;
}

4. 就地逆置法

就地逆置法与头插法的区别就在于是否构造新串。就地逆置法的插入操作直接在原来的单链表上进行。所以相比头插法,就地逆置法还需要多用一个指针。

1
2
3
4
5
6
7
8
9
10
LinkListNode * LinkListReverse_4(LinkListNode * head){
LinkListNode * p=head->next, * q=p->next;
while(q!=NULL){
p->next=q->next;
q->next=head->next;
head->next=q;
q=p->next;
}
return head;
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct LinkListNode{
DataType data;
struct LinkListNode * next;
}LinkListNode,*ListPtr;

LinkListNode * InitLinkList(int n);
LinkListNode * LinkListReverse_1(LinkListNode * head);
LinkListNode * LinkListReverse_3(LinkListNode * head);
LinkListNode * LinkListReverse_4(LinkListNode * head);
int DisplayLinkList(LinkListNode * head);

int main(){
int n=9;
LinkListNode * head;
head=InitLinkList(n);
printf("原始的序列:");
DisplayLinkList(head);

head=LinkListReverse_1(head);
printf("交换第一次后的序列:");
DisplayLinkList(head);

head=LinkListReverse_3(head);
printf("交换第二次后的序列:");
DisplayLinkList(head);

head=LinkListReverse_4(head);
printf("交换第三次后的序列:");
DisplayLinkList(head);

return 0;
}

LinkListNode * InitLinkList(int n){
LinkListNode * head=(LinkListNode*)malloc(sizeof(LinkListNode));
if(head==NULL) exit(0);
head->next=NULL;
LinkListNode * temp=head;
for(int i=1;i<=n;i++){
temp->next=(LinkListNode*)malloc(sizeof(LinkListNode));
if(temp->next==NULL) exit(0);
temp=temp->next;
temp->next=NULL;
temp->data=i;
}
return head;
}
int DisplayLinkList(LinkListNode * head){
LinkListNode * temp=head->next;
while(temp!=NULL){
printf("%d",temp->data);
temp=temp->next;
}
printf("\n");
return 0;
}
LinkListNode * LinkListReverse_1(LinkListNode * head){
LinkListNode * cur=head->next;
LinkListNode * pre=NULL, * nex=NULL;
while(cur!=NULL){
nex=cur->next;
cur->next=pre;
pre=cur;
cur=nex;
}
head->next=pre;
return head;
}

LinkListNode * LinkListReverse_3(LinkListNode * head){
if(head->next==NULL||head->next->next==NULL) return head;
LinkListNode * list=(LinkListNode*)malloc(sizeof(LinkListNode));
list->next=NULL;
LinkListNode * temp;
while(head->next!=NULL){
temp=head->next;
head->next=temp->next;
temp->next=list->next;
list->next=temp;
}
return list;
}
LinkListNode * LinkListReverse_4(LinkListNode * head){
LinkListNode * p=head->next, * q=p->next;
while(q!=NULL){
p->next=q->next;
q->next=head->next;
head->next=q;
q=p->next;
}
return head;
}

output:

1
2
3
4
原始的序列:123456789
交换第一次后的序列:987654321
交换第二次后的序列:123456789
交换第三次后的序列:987654321

递归法的链表因为不带头结点,所以没有测试,不过应该没问题。