19年数据结构考察了一道链表的题，本篇文章将带来两种算法的实现：递归和分链重排。为了大家更好的理解，我会附上较为清晰的图解与关键代码注释，分析两种算法的时间复杂度。

0、链表初始化及尾插建表

// 定义结构体
typedef struct LNode {
int data;
struct LNode* next;
}LNode ,*LinkList;
// 初始化，让链表带有头结点
void Init_List(LinkList &L) {
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
}
// 尾插建表
void post_create(LinkList L) {
LinkList p = L;
LinkList s = NULL;
int x;
cin >> x;
int y;
while (x--) {
cin >> y;
s = (LinkList)malloc(sizeof(LNode));
s->data = y;
s->next = NULL;
p->next = s;
p = s;
}
p = NULL;
free(p);
}
// 打印链表函数
void print(LinkList L) {
LinkList p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
cout << endl;
}
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

由于使用了typedef的缘故，这里的LinkList等价于struct LNode *，LNode 等价于 struct LNode。

注意初始化函数里的参数要引用 &，凡是在函数里改变了指向链表的地址，都需要加引用。

1、递归解法

设计思想：
根据题目中 L` 的特点可以看出：我们可以让链表 L 的每个表尾结点插入到首元结点(头结点后的第一个结点)之后，更新首元结点与表尾结点，重复操作，这就是递归的分析。

图示：
比如原来链表元素为：1 2 3 4 5 6 7，递归后变为：1 7 2 6 3 5 4。

代码实现：

void rearrangedList(LinkList L) {
if (!L || !L->next || !L->next->next) return; //结束条件之一
LinkList p = L; // 用于找到链表的倒数第二个结点
LinkList head = L->next; // 表示首元结点
while (p->next->next) {
p = p->next; // 此时p为倒数第二个结点
}
if (p == head) return; // 结束条件之二
p->next->next = head->next; // 最后一个结点指向首元结点的下一个结点
head->next = p->next; // 首元结点指向最后一个结点，就是插入操作
p->next = NULL; // 最后一个结点置为空，防止重复寻找倒数第二个结点
rearrangedList(head->next); // 每次插入的表尾结点充当头结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13

代码解析：
这里的结束条件之二需要特别解释一下：

当链表元素为偶数个时会出现首元结点 head 和 倒数第二个结点 p 指向相同，实际上满足这个条件的话，链表已经完成了重排，即已经达到了题目要求的效果。

递归最重要的就是找到递归终止的条件，对于本题来说：
如果头结点为空、或者链表中只有一个结点那都是不用进行重排的，因此可当成递归的终止条件

1.1、递归解法测试运行

void test_rearrangedList() {
LinkList L; 
Init_List(L); // 初始化
post_create(L); // 后插建表
rearrangedList(L); // 调用递归算法
print(L); // 打印链表
}
1
2
3
4
5
6
7

运行截图：

1.2、递归的时间复杂度分析

分析时间复杂度就要找代码中执行次数最多的那一部分，毫无疑问，while 里的语句执行的最多，p 每次都要指向链表中的倒数第二个位置，递归的结点是递归前头结点的下下个结点，因此可以粗略看成是公差为 2 ，首项为 0 的等差数列前 n 项和：$\frac{n(0+(n-1)\ast 2)}{2}=n^2-n$，因此时间复杂度为$O(n^2)$。

2、分链、逆转、合并（最优解）

这是本题的最优解：

1. 把整个链表分为两部分
2. 后半部分链表需要原地逆置(保证空间复杂度为$O(1)$)
3. 交叉合并这两部分链表

2.1、双指针法求中间结点并分链

// 寻找中间结点并返回第二条链表
void find_middle(LinkList L, LinkList L2) {
LinkList ppre = L->next; // 双指针考研常考
LinkList pcur = L->next;
while (pcur->next) {
pcur = pcur->next;
if (pcur->next==NULL) {
break;
}else pcur = pcur->next;
ppre = ppre->next;
}
L2->next = ppre->next;
ppre->next = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

pcur 为快指针，ppre为慢指针，前者一次走两步，后者走一步，但是需要判断第二步能否走得了，防止出现 $pcur=NULL->next$ ，这种情况肯定是错误的。

2.2、链表的原地逆置实现

void reverse_list(LinkList L2) {
LinkList pre, cur,ptr;
pre = L2->next;
if (NULL == pre) return;
cur = pre->next;
if (NULL == cur) return;
ptr = cur->next;
while (ptr) {
cur->next = pre;
pre = cur;
cur = ptr;
ptr = ptr->next;
}
cur->next = pre;
L2->next->next = NULL; //非常重要，代表着重置后的最后一个结点的next设为NULL
L2->next = cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

编码风格推荐：我们在写判断条件的时候，建议NULL写在双等号前面，当我们误写成等号的时候编译器就会提示错误。

只看代码可能不好理解这个逻辑，我们用图来分析：

开始时链表的顺序为：L 1 2 3 NULL，逆置后变为：L 3 2 1 NULL。

L2->next->next = NULL 是把结点1的后继设为NULL，必须要写在L2->next = cur前面。

2.3、合并链表

实现思想：
每次将 L2 中的结点插入到 L1 中，更新 L2 的结点，直到两个链表为空。

代码实现：

void merge(LinkList L1, LinkList L2) {
LinkList p1 = L1->next;
LinkList p2 = L2->next;
LinkList cur = p2->next;
while (p1 && p2) {
p2->next = p1->next;
p1->next = p2;
p1 = p2->next;
p2 = cur;
if (cur != NULL) cur = cur->next;// 防止出现cur = NULL->next
else break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.4、测试运行

void test_merge() {
LinkList L;
LinkList L2;
Init_List(L);
Init_List(L2);
post_create(L);
find_middle(L, L2); // 调用分链
reverse_list(L2);   // 逆置L2
print(L);
print(L2);
merge(L, L2);    // 合并
print(L);// 最终打印
}
1
2
3
4
5
6
7
8
9
10
11
12
13

运行截图：

2.5、时间复杂度分析

三个函数互不嵌套，顺序执行：

• 分链是找到中间结点，时间复杂度为$O(\frac{n}{2})$
• 逆置是将整个链表原地逆转，时间复杂度为$O(\frac{n}{2})$(结点为原来的一半)
• 合并是遍历两个链表，时间复杂度也是$O(\frac{n}{2})$

因此最优解的时间复杂度为$O(n)$。