1105 链表合并——PAT乙级

本文主要是介绍1105 链表合并——PAT乙级，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

 solution:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int maxn=1e5+5;
int main()
{int start1,start2,n;cin>>start1>>start2>>n;int data[maxn],next[maxn];for(int i=0;i<n;i++){int tmp;cin>>tmp;cin>>data[tmp]>>next[tmp];}vector<pair<int,int> >list1,list2;int cnt1=0,cnt2=0;while(start1!=-1){cnt1++;list1.push_back({start1,data[start1]});start1=next[start1];}while(start2!=-1){cnt2++;list2.push_back({start2,data[start2]});start2=next[start2];}if(cnt1<cnt2)//交换大小后，list的长度也需要交换 {swap(list1,list2);swap(cnt1,cnt2);}//reverse(list2.begin(),list2.end());//整理，这句反转不需要，因为之后j倒序输入 vector<pair<int,int> >ans;int i=0;int j=cnt2-1;while(i<cnt1 || j>=0){if(i<cnt1){ans.push_back({list1[i].first,list1[i].second});i++;}if(i<cnt1){ans.push_back({list1[i].first,list1[i].second});i++;}if(j>=0){ans.push_back({list2[j].first,list2[j].second});//反转 j--;}}for(int i=0;i<ans.size()-1;i++){printf("%05d %d %05d\n",ans[i].first,ans[i].second,ans[i+1].first);}printf("%05d %d -1\n",ans[ans.size()-1].first,ans[ans.size()-1].second);return 0;
}

这篇关于1105 链表合并——PAT乙级的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---