首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#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 &lt;bits/stdc++.h&gt; using namespace std; #define MAX 100005 struct LinkNode {     int address;   //当前结点的地址     int data;      //当前结点的数据     int next;      //下一结点的地址 }node[MAX]; int main() {     int Head,N;   //头结点Head、结点总个数N     cin &gt;&gt; Head &gt;&gt; N;     for(int i = 0; i &lt; N; i++)     {         int temp;         cin &gt;&gt; temp;         node[temp].address = temp;         cin &gt;&gt; node[temp].data &gt;&gt; node[temp].next;     }      vector&lt;LinkNode&gt; 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 &lt; l) break;  //当r出现在l左侧时说明链表重排完成         ans.push_back(v[l]);         l++;         if(r &lt; l) break;  //当r出现在l左侧时说明链表重排完成     }     for(int i = 0; i &lt; 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>
这道题暂未补解析。