A1162 Merging Linked Lists (25 points)

链表合并

1. 原文

Given two singly linked lists L₁ =a₁ →a₂ →…→a_n-1 →a_n and L₂ =b₁ →b₂ →…→b_m-1 →b_m. You are supposed to reverse and merge the shorter one into the longer one to obtain a list like a₁ →a₂ →b_m →a₃→a₄ →b_m-1… For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.

1.0.1. Input Specification

Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L1and L2 , plus a positive N(≤$10^5$ ) which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is a positive integer no more than $10^5$ , and Next is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.

Output Specification

For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input

00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1

Sample Output

01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

2. 解析思路

先按照链表顺序创建出两个链表

按照链表的长度，长的每次取两个，从头开始取，短的每次取一个，从尾开始取

3. AC代码

#include<cstdio>
#include<map>
#include<vector>
using namespace std;
map<int,int> data,nextAdd;
vector<int> v1,v2,ans;
int main(){
	int f1,f2,n;
	scanf("%d%d%d",&f1,&f2,&n);
	for (int i = 0; i < n; ++i)
	{
		int a;
		scanf("%d",&a);
		scanf("%d%d",&data[a],&nextAdd[a]);
	}
	int len1 = 0;
	int len2 = 0;
	for (int i = f1; i != -1; i=nextAdd[i])
	{
		len1++;
		v1.push_back(i);
	}
	for (int i = f2; i != -1; i=nextAdd[i])
	{
		len2++;
		v2.push_back(i);
	}

	if (len1>len2)
	{
		int i = 0;
		int j = len2-1;
		while(i<len1&&j>=0){
			ans.push_back(v1[i++]);
			ans.push_back(v1[i++]);
			ans.push_back(v2[j--]);
		}
		while(i<len1){
			ans.push_back(v1[i++]);
		}
		while(j>=0){
			ans.push_back(v2[j--]);
		}
	}else{
		int i = 0;
		int j = len1-1;
		while(i<len2&&j>=0){
			ans.push_back(v2[i++]);
			ans.push_back(v2[i++]);
			ans.push_back(v1[j--]);
		}
		while(i<len2){
			ans.push_back(v2[i++]);
		}
		while(j>=0){
			ans.push_back(v1[j--]);
		}
	}
	for (int i = 0; i < ans.size(); ++i)
	{
		if (i!=ans.size()-1)
		{
			printf("%05d %d %05d\n",ans[i],data[ans[i]],ans[i+1]);
		}else{
			printf("%05d %d -1\n", ans[i],data[ans[i]]);
		}
	}
	return 0;
}