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是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式：

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

输入样例：

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，数据data，下一个元素next。然后设置一个根结点root和尾结点tail，分别指向第一个结点地址和最后一个结点地址。先输出tail，tail指向对应上一个元素pre。再输出root，root指向对应下一个元素next，以此循环。直到tail与root相遇时输出tail，终止循环。输出tail对应数据时，可以输出tail，data，root，输出root对应数据时，可以输出root，data，tail。

#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;  
}