简答题
偏难
#7548
重链重排 给定一个单链表 L1→L2→…→Ln-1→Ln,请编写程序将链表重新排列为 Ln→L1→Ln-1→L2→…。例如:给定L为1→2→3→4→5→6,则输…
重链重排
给定一个单链表 L1→L2→…→Ln-1→Ln,请编写程序将链表重新排列为 Ln→L1→Ln-1→L2→…。例如:给定L为1→2→3→4→5→6,则输出应该为6→1→5→2→4→3。
时间限制:1000
内存限制:65536
输入
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数,即正整数N (≤ 105)。结点的地址是5位非负整数,NULL地址用-1表示。 接下来有N行,每行格式为: Address Data Next 其中`Address`是结点地址;`Data`是该结点保存的数据,为不超过105的正整数;`Next`是下一结点的地址。题目保证给出的链表上至少有两个结点。
输出
对每个测试用例,顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。
样例输入
00100 6 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218
样例输出
68237 6 00100 00100 1 99999 99999 5 12309 12309 2 00000 00000 4 33218 33218 3 -1
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
struct LinkNode
{
int address; //当前结点的地址
int data; //当前结点的数据
int next; //下一结点的地址
}node[MAX];
int main()
{
int Head,N; //头结点Head、结点总个数N
cin >> Head >> N;
for(int i = 0; i < N; i++)
{
int temp;
cin >> temp;
node[temp].address = temp;
cin >> node[temp].data >> node[temp].next;
}
vector<LinkNode> v,ans;
for(int i = Head; i != -1; i = node[i].next) //先根据地址来将链表排序
{
v.push_back(node[i]);
}
int l = 0, r = v.size()-1;
while(true) //链表重排
{
ans.push_back(v[r]);
r--;
if(r < l) break; //当r出现在l左侧时说明链表重排完成
ans.push_back(v[l]);
l++;
if(r < l) break; //当r出现在l左侧时说明链表重排完成
}
for(int i = 0; i < ans.size(); i++)
{
if(i != ans.size()-1)
{
printf("%05d %d %05d\n",ans[i].address,ans[i].data,ans[i+1].address);
}
else
{
printf("%05d %d -1\n",ans[i].address,ans[i].data);
}
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。