团体程序设计天梯赛-练习集 L2-022 重排链表 (25分) 模拟思想坑点分析

我会带着你远行 2023-10-11 15:06 35阅读 0赞

### L2-022 重排链表 (25分) ###

给定一个单链表 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

--------------------

##### 分析： #####

题目采用模拟就可做出来，但是坑点很多：

1.  测试点 2 在模拟实际节点数组的时候，奇数个时**要进入if(left==right)\{ b\[k++\] = a\[right–\]; // 或者是 b\[k++\] = a\[left++\]\}因为要循环结束的条件为left<=right**，因此需要**right–或者是left++**;否则会发生测试点2的段错误！
2.  测试点 3，可能存在多个next值为-1的情况，因此采用模拟数组的大小输出即可，即实际节点的个数输出，而不能采用刚开始输入的n。

类似题目可参考：[L2-002 链表去重 (25分) 模拟思想][L2-002 _ _25_]

#include<bits/stdc++.h>
    #define Inf 0x3f3f3f
    const int N = 100005;
    using namespace std;
    
    struct node{
        
    	int data;
    	int next;
    }li[N];
    int n, first, k;
    int add, da, ne;
    int a[N], b[N];
    
    int main(){
        
    	cin >> first >> n;
    	while(n--){
        
    		cin >> add >> da >> ne;
    		li[add].data = da;
    		li[add].next = ne;
    	}
    
    	k = 0;
    	while(first != -1){
        
    		a[k++] = first;
    		first = li[first].next;
    	}
    
    	int left = 0, right = k - 1;
    	k = 0;
    	while(left <= right){
        
    		if(left == right){
        
    			b[k++] = a[right--]; //一定要right--或者是 b[k++] = a[left++]
    		}else{
        
    			b[k++] = a[right--];
    			b[k++] = a[left++];
    		}
    	}
    
    	for(int i = 0; i < k-1; i ++){
        
    		printf("%05d %d %05d\n", b[i], li[b[i]].data, b[i+1]);
    	}
    	printf("%05d %d -1\n", b[k-1], li[b[k-1]].data);
    
    	return 0;
    }

[L2-002 _ _25_]: https://blog.csdn.net/weixin_43819566/article/details/109087602