原题链接
原题链接
题意分析
给定一个链表，按照从尾端取一个，从头端取一个的规律重新排列链表，直至将原链表的所有元素都重新排列完。
思路分析
第一步，先将每个结点的数据按照输入顺序存下。
第二步，按照输入的逻辑的先后顺序，将结点连成一整条链表。
第三步，重排链表，并将其输出。
如：
橙色格子中的数字表示链表结点的下标，箭头指向的是该结点的后继。
链表的最后一个元素输出时，下一个节点的地址为-不用补前导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;
}
文章为作者独立观点，不代表 股票程序化软件自动交易接口观点
股民评论