[数据结构与算法]PAT乙级 1105 链表合并 (25 分)

给定两个单链表?L1?=a1?→a2?→?→an?1?→an??和?L2?=b1?→b2?→?→bm?1?→bm?。如果?n≥2m，你的任务是将比较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如?a1?→a2?→bm?→a3?→a4?→bm?1???的结果。例如给定两个链表分别为 6→7 和 1→2→3→4→5，你应该输出 1→2→7→3→4→6→5。

输入格式：

输入首先在第一行中给出两个链表?L1??和?L2??的头结点的地址，以及正整数?N?(≤105)，即给定的结点总数。一个结点的地址是一个 5 位数的非负整数，空地址 NULL 用?-1?表示。

随后?N?行，每行按以下格式给出一个结点的信息：

Address Data Next

其中?Address?是结点的地址，Data?是不超过?105?的正整数，Next?是下一个结点的地址。题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。

输出格式：

按顺序输出结果链表，每个结点占一行，格式与输入相同。

输入样例：

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

输出样例：

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

?思路

1.用结构体数组模拟链表 按照题目遍历链表 将结点地址放入v1,v2中

2.如果v1.size() <? v2.size() 则交换v1,v2

? ?当v1.size() >= v2.size() * 2 用reverse反转v2

3.按题意 遍历v1, v1中每隔2个结点就插入一个v2中的结点并用temp计数

? ?注意要判断temp!=v2.size()时要添加一个尾结点

4.最后按题意输出即可

AC代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 100000;

struct node
{
	int address, data, next;
}nodep[MAXN];

int main()
{
	int address1, address2, n;
	cin >> address1 >> address2 >> n;
	for (int i = 0; i < n; i++) {
		int address;
		cin >> address;
		cin >> nodep[address].data >> nodep[address].next;
	}
	vector<int>v1, v2;
	for (int i = address1; i != -1; i = nodep[i].next) {
		v1.push_back(i);
	}
	for (int i = address2; i != -1; i = nodep[i].next) {
		v2.push_back(i);
	}
	if (v1.size() < v2.size()) swap(v1, v2);
	if (v1.size() >= v2.size() * 2) reverse(v2.begin(), v2.end());
	int cnt = 0, temp = 0;
	for (int i = 0; i < v1.size(); i++) {
		cnt++;
		if (cnt == 3 && temp < v2.size()) {
			cnt = 0;
			v1.insert(v1.begin() + i, v2[temp++]);
		}
	}
	if (temp != v2.size()) v1.push_back(v2[temp++]);
	for (int i = 0; i < v1.size() - 1; i++) {
		printf("%05d %d %05d\n", v1[i], nodep[v1[i]].data, v1[i + 1]);
	}
	printf("%05d %d -1\n", v1[v1.size() - 1], nodep[v1[v1.size() - 1]].data);
	return 0;
}