【线性表的原地逆置】

前言

打怪升级第一天：
大家好，今天我们来了解一下数组和单链表的原地逆置问题。
那么首先：何为原地逆置？
就是在不创建额外的数组或链表，在空间复杂度为O（1）的情况下完成逆置，
下面我们实际操作起来。

---

一、顺序表（数组）

（一）双指针

示例：

void Reverse(int arr[], int n)
{
	int left = 0;//可以使用指针，也可以使用下标
	int right = n - 1;
	while (left < right)//左右下标重合表明交换完毕
	{
		int con = arr[left];
		arr[left] = arr[right];
		arr[right] = con;
		left++;
		right--;
	}
}

int main()
{
	int arr[100] = { 0 };
	printf("请输入数组元素的个数：");
	int n = 0;
	scanf("%d", &n);
	int  i = 0;
	for (i = 0; i < n; i++)
		scanf("%d", arr + i);

	Reverse(arr, n);

	printf("逆置结果：");
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
	printf("\n");

	return 0;
}
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

图解 + 运行实例：

---

二、单链表

（一）模拟顺序表的双指针（交换的节点的值域）

为了方便阅读，前面只给出主要代码，整体代码会放到文章最后。

示例：

//模拟顺序表双指针
void Reverse(LN* left, int num)
{
	int con = 0;
	while (con < num / 2)
	{
		LN* right = left;
		int i = 1;
		while (i < num - 2 * con)//寻找需要交换的右边的节点
		{
			right = right->next;
			i++;
		}
		int tmp = left->data;
		left->data = right->data;
		right->data = tmp;
		left = left->next;
		con++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

图解：

（二）头插法（改变节点的指针域）

示例：

//打断链表，以头插法进行插入
void Reverse(LN* ph)
{
	LN* paim;//需要插入的节点
	LN* ptr;//下一个节点
	paim = ph->next;
	ph->next = NULL;//先将头结点置空，之后在头结点之后进行插入
	while (paim)
	{
		ptr = paim->next;
		paim->next = ph->next;
		ph->next = paim;
		paim = ptr;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

图解：

（三）递归实现（将整体链表反向）

示例：

//递归实现，由于无法从后一个节点找到前一个节点，所以从倒数第二个节点开始操作
LN* Reverse(LN* ph)
{
	if (ph == NULL || ph->next == NULL)//终止递归的条件
	{
		return ph;//最后一个节点不在这一步进行操作
	}
	LN* pend = Reverse(ph->next);
	ph->next->next = ph;
	ph->next = NULL;
	return pend;//返回最后一个节点的指针
}
1
2
3
4
5
6
7
8
9
10
11
12

图解：

整体代码

#define MALLOC(ty,num) (ty*)malloc(sizeof(ty)*(num))

//原地逆序：单链表

typedef struct LinkedNode
{
	int data;
	struct LinkedNode* next;
}LN;
 
void Init(LN* ph, int num)
{
	for (int i = 0; i < num; i++)
	{
		LN* ptr = MALLOC(LN, 1);
		if (ptr == NULL)
		{
			perror("Init::MALLOC");
			exit(1);
		}
		printf("请输入第%d个节点值：", i + 1);
		scanf("%d", &ptr->data);
		ptr->next = NULL;
		ph->next = ptr;
		ph = ptr;
	}
}

void Print(LN* ph)
{
	LN* p = ph->next;
  printf("结果：");
	while (p != NULL)
	{
		printf("%d ", p->data);
		ph = p;
		p = p->next;
		free(ph);
	}
}

//递归实现，由于无法从后一个节点找到前一个节点，所以从倒数第二个节点开始操作
LN* Reverse(LN* ph)
{
	if (ph == NULL || ph->next == NULL)//终止递归的条件
	{
		return ph;
	}
	LN* pend = Reverse(ph->next);
	ph->next->next = ph;
	ph->next = NULL;
	return pend;//返回最后一个节点的指针
}

打断链表，以头插法一个一个得插入
//void Reverse(LN* ph)
//{
//	LN* paim;//即将插入的节点
//	LN* ptr;//下一个节点
//	paim = ph->next;
//	ph->next = NULL;
//	while (paim)
//	{
//		ptr = paim->next;
//		paim->next = ph->next;
//		ph->next = paim;
//		paim = ptr;
//	}
//}

在变化过程中链表一直未打断，，但是过于复杂
//void Reverse(LN* ph)
//{
//	
//	LN* ptr = ph->next;
//	while (ptr->next)
//	{
//		LN* p1 = ph->next;
//		LN* p2 = ptr->next;
//		ph->next = ptr->next;
//		ptr->next = ptr->next->next;
//		p2->next = p1;
//	}
//}

模拟顺序表双指针
//void Reverse(LN* left, int num)
//{
//	int con = 0;
//	while (con < num / 2)
//	{
//		LN* right = left;
//		int i = 1;
//		while (i < num - 2 * con)//寻找需要交换的右边的节点
//		{
//			right = right->next;
//			i++;
//		}
//		int tmp = left->data;
//		left->data = right->data;
//		right->data = tmp;
//		left = left->next;
//		con++;
//	}
//}

//带头单链表：原地逆置
int main()
{
	LN* head = MALLOC(LN, 1);//头结点
	if (head == NULL)
	{
		perror("main::MALLOC");
		exit(1);
	}
	head->next = NULL;
	printf("请输入与节点个数：");
	int num = 0;
	scanf("%d", &num);
	Init(head, num);
	//Reverse(head->next, num);
	//Reverse(head);
	head->next = Reverse(head->next);//从头结点后一个节点开始逆置
	Print(head);
	free(head);
	return 0;
}
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

运行实例：

---

总结

以上就是今天讲解的线性表逆置的全部内容，如果有什么疑问或者建议都可以在评论区留言，感谢大家对的支持。