【天梯赛】L2-022 重排链表 (25分)

我会带着你远行 2022-12-24 10:59 174阅读 0赞

**题目描述**  
给定一个单链表 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 (≤10^5 )。结点的地址是5位非负整数，NULL地址用−1表示。

接下来有N行，每行格式为：  
`Address Data Next`  
其中Address是结点地址；Data是该结点保存的数据，为不超过10  
^5 的正整数；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

**设置一个node结构体存储节点的键值和下一个节点的地址；分别设ans\[10005\] 和 res\[100005\]存储原链表和重新排序后的链表；然后顺序输出就可以了。**

## 链表排序还原 ##

int ans[100005], k = 0;//存储原来的链表
    	int p = head;
    	while(p != -1){
        
    		ans[k++] = p;
    		p = list[p].next;
    	}

## AC代码 ##

#include <iostream>
    using namespace std;
    struct node{
        
    	int data, next;
    }list[100005];
    int main() {
        
    	int head, n;
    	cin >> head >> n;
    	while(n--){
        
    		int add;
    		cin >> add;
    		cin >> list[add].data >> list[add].next;
    	}
    	int ans[100005], k = 0;//存储原来的链表
    	int p = head;
    	while(p != -1){
        
    		ans[k++] = p;
    		p = list[p].next;
    	}
    	int res[100005], k2 = 0;  //存储新的链表
    	for(int i = k-1; i > 0; i--){
        
    		res[k2++] = ans[i];
    		res[k2++] = ans[k-1-i];
    		if(k2 == k) break;
    	}
    	for(int i = 1; i < k; i++){
        
    		printf("%05d %d %05d\n",res[i-1], list[res[i-1]].data, res[i]); 
    	}
    	printf("%05d %d -1\n",res[k-1], list[res[k-1]].data);
    }