2019年408数据结构第41题分析与实现

微凉秋意 2023-05-09 原文

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

由于使用了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); // 每次插入的表尾结点充当头结点
}

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

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

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

1.1、递归解法测试运行

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

运行截图：

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

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

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

这是本题的最优解：

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

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

pcur 为快指针，ppre为慢指针，前者一次走两步，后者走一步，但是需要判断第二步能否走得了，防止出现 $p c u r = N ULL - > n e x t$ ，这种情况肯定是错误的。

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

编码风格推荐：我们在写判断条件的时候，建议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;
	}
}

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);					// 最终打印
}