[数据结构]L2-022. 重排链表

L2-022. 重排链表

给定一个单链表 L1→L2→…→Ln-1→Ln,请编写程序将链表重新排列为 Ln→L1→Ln-1→L2→…。例如:给定L为1→2→3→4→5→6,则输出应该为6→1→5→2→4→3。

输入格式:

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数,即正整数N (<= 105)。结点的地址是5位非负整数,NULL地址用-1表示。

接下来有N行,每行格式为:

Address Data Next

其中Address是结点地址;Data是该结点保存的数据,为不超过105的正整数;Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式:

对每个测试用例,顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。

输入样例:

1
2
3
4
5
6
7
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例:

1
2
3
4
5
6
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

分析:

一道数据结构链表题。由于每一次输出链表两边的元素,因此可以构建一个双向链表。即结构体中储存上一个元素pre,数据data,下一个元素next。然后设置一个根结点root和尾结点tail,分别指向第一个结点地址和最后一个结点地址。先输出tail,tail指向对应上一个元素pre。再输出root,root指向对应下一个元素next,以此循环。直到tail与root相遇时输出tail,终止循环。输出tail对应数据时,可以输出tail,data,root,输出root对应数据时,可以输出root,data,tail。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>  
#define Maxn 100000
using namespace std;
struct Lists {
int pre;
int data;
int next;
Lists() {
pre = -1;
data = 0;
next = -1;
}
}List[Maxn];
int main() {
int root, N, tail;
scanf("%d%d", &root, &N);
for (int i = 0; i < N; i++) {
int temp;
scanf("%d", &temp);
scanf("%d%d", &List[temp].data, &List[temp].next);
if (List[temp].next != -1)
List[List[temp].next].pre = temp;
else
tail = temp;
}
int flag = 0;
while (root != tail) {
printf("%05d %d %05d\n", tail, List[tail].data, root);
tail = List[tail].pre;
if (root == tail)
break;
printf("%05d %d %05d\n", root, List[root].data, tail);
root = List[root].next;
}
printf("%05d %d -1\n", root, List[root].data);
return 0;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!