上交所股票交易数据接口-PTA团体程序设计天梯赛L2002重排链表

原题链接

题意分析

给定一个链表，按照从尾端取一个，从头端取一个的规律重新排列链表，直至将原链表的所有元素都重新排列完。

思路分析

第一步，先将每个结点的数据按照输入顺序存下。

第二步，按照输入的逻辑的先后顺序，将结点连成一整条链表。

第三步，重排链表，并将其输出。

如：

橙色格子中的数字表示链表结点的下标，箭头指向的是该结点的后继。

链表的最后一个元素输出时，下一个节点的地址为-不用补前导0。

重新排列链表之后，每个结点的后继结点也会随之发生改变。

在第二步的时候，为了方便查找每个结点的结点，将结点按照存储地址从小到大进行了排序，并使用了二分查找的方法。

本题的测试点输入的结点，并非全都属于同一条链表。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int n;//总的结点数 

struct aa {
	int ad , next;//当前结点地址 ，后继结点地址 
	int data;// 当前结点数据 
}a[N] , b[N];

bool cmp (struct aa x , struct aa y) {
	return x.ad <= y.ad;
	//若是x的地址比y的小，或者和y的地址相等，则返回true
	//反之，返回false 
}

int find (int key) {//二分查找函数 
	int l = 0 , r = n-1 , mid;
	
	while (l < r) {
		mid = (l + r + 1) / 2;
		if (a[mid].ad > key) r = mid - 1;
		else l = mid;
	}
	
	return l;
}

int main () {
	int h;//头结点地址 
	int num;
	cin >> h >> n;
	
	for (int i = 0 ; i < n ; i ++) //输入每个结点 
		cin >> a[i].ad >> a[i].data >> a[i].next; 
	
	sort (a , a+n , cmp);//结构体排序 
	
	num = find (h);//要找的地址在a中所对应的下标 
	b[1] = a[num];//将原链表存进b中
	 
	for (int i = 2 ; i <= n ; i ++) {
		num = find (b[i-1].next);//当前结点，为前一个结点的后继 
		b[i] = a[num];
		
		if (b[i].next == -1) n = i;//若当前结点无后继，则当前链表已结束 
	}
	
	int l = 1 , r = n;
	while (l < r) {
		printf ("%05d %d %05d
" , b[r].ad , b[r].data , b[l].ad);//先输出尾端结点
		//当前尾端结点的后继为相对应的头端结点 
		 
		if (r-1 != l) //若非最后一个结点，那么当前头端结点的后继结点为下一组尾端结点 
			printf ("%05d %d %05d
" , b[l].ad , b[l].data , b[r-1].ad);
		else // 若是r-1==l,则说明现在的头端结点为链表的最后一个结点 
			printf ("%05d %d -1
" , b[l].ad , b[l].data);
			
		l ++ , r --;//下一组头尾端结点的下标 
	} 
	if (l == r) //若当前链表的结点长度为奇数，那么上面的循环将不会输出处于中间位置的结点 
		printf ("%05d %d -1
" , b[l].ad , b[l].data);
	
	return 0;
}

文章为作者独立观点，不代表股票程序化软件自动交易接口观点