T O P

[资源分享]     PTA 重排链表(数组法)

  • By - 楼主

  • 2019-09-19 15:25:01
  • 给定一个单链表 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
    

    实现代码:

    #include<iostream>
    #define MAX 100001
    using namespace std;
    struct LinkNode {
    	int data;
    	int next;//下一个元素的地址
    };
    int main(void) {
    	int i, j, n, FirstAddress, Data, Address, Next;//FirstAddress 第一个地址的值,
    	int address1[MAX];//顺序保存原始地址数据
    	int address2[MAX];//保存重排之后地址数据
    	int length, count = 0;//length节点数,count计数
    	struct LinkNode add[MAX];
    	cin >> FirstAddress >> n;//首地址和节点数
    	for (i = 0; i < n; i++) {
    		cin >> Address >> Data >> Next;
    		add[Address].data = Data;
    		add[Address].next = Next;
    	}
    	while (FirstAddress != -1) {//按节点顺序保存地址数据于address1
    		address1[count++] = FirstAddress;
    		FirstAddress = add[FirstAddress].next;
    	}
    	length = count;
    	for (i = 0, j = length - 1, count = 0; i <= j;)//开始重排
    		if (i == j) {//当节点数为奇数时,i=j
    			address2[count] = address1[i];
    			break;
    		}
    		else {
    			address2[count++] = address1[j--];
    			address2[count++] = address1[i++];
    	     }
    	for (i = 0; i < length - 1; i++)
    		printf("%05d %d %05d\n", address2[i], add[address2[i]].data, address2[i + 1]);
    	printf("%05d %d -1\n", address2[length - 1], add[address2[length - 1]].data);//控制最后输出-1
    
    	return 0;
    }
    

    本帖子中包含资源

    您需要 登录 才可以下载,没有帐号?立即注册