一道数据结构算法设计题

一道数据结构算法设计题 题目

线性表 L = [ a 1 , a 2 , a 3 , . . . , a n − 2 , a n − 1 , a n ] L=[a_1,a_2 , a_3,...,a_{n-2},a_{n-1},a_{n} ] L=[a1​,a2​,a3​,...,an−2​,an−1​,an​]采用带头节点的单链表保存，链表中结点定义如下：

typedef struct Node{
	int data;
	struct Node *next;
}Node,*linkList;

请设计一个空间复杂度为 O ( 1 ) O(1) O(1)，且时间上尽可能高效的算法，重新排列 L L L中的各结点，得到线性表 L ′ = [ a 1 , a n , a 2 , a n − 1 , a 3 , a n − 2 , . . . ] L'=[a_1,a_n,a_2,a_{n-1},a_3,a_{n-2},...] L′=[a1​,an​,a2​,an−1​,a3​,an−2​,...]

要求：

1. 给出算法的基本设计思想
2. 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释
3. 说明你所设计的算法的时间复杂度

思路

设计两个函数：

1. 翻转链表，时间复杂度 O ( n ) O(n) O(n)
2. 交叉合并链表，时间复杂度 O ( m a x ( m , n ) ) O(max(m,n)) O(max(m,n))

将原链表从中间分开，将后半部分翻转后，再与前半部分交叉合并。具体代码实现如下：

linkList reverse(linkList L){
	//翻转链表（不含头结点）
	linkList head=NULL;
	while(L){
		Node* tmp=L;
		L=L->next;
		tmp->next=head;
		head=tmp;
	}//头插法，将链表翻转
	return head;
}

linkList merge(linkList a,linkList b){
	//交叉合并两个链表（不含头结点）
	linkList c=new Node;
	Node *p=a,*q=b,*tail=c;
	while(p||q){
		if(p){
			tail=tail->next=p;
			p=p->next;
		}
		if(q){
			tail=tail->next=q;
			q=q->next;
		}
	}
	return c->next;
}

linkList func(linkList L){
	//链表含头结点
	Node *end=L->next,*mid=L->next,*last=L;
	//end指向链表尾，mid指向中间结点，last指向mid的前一个结点 
	while(end){
		mid=mid->next;
		last=last->next;
		end=end->next;
		if(end)end=end->next;
	}//寻找链表的中间结点
	last->next=NULL;//断开成两个链表 
	mid=reverse(mid);//翻转后半部分 
	L->next=merge(L->next,mid);//交叉合并 
	return L;
}

算法总体时间复杂度为 O ( n ) O(n) O(n)