7-2 Merging Linked Lists (25 分)

本文主要是介绍7-2 Merging Linked Lists (25 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考查的知识点：
链表的静态存储
PAT的经典类型题

#include <iostream>
#include <cstdio>
#include <stack>
#include <unordered_map> 
#include <algorithm> 
using namespace std;
const int N =1e5+3;
struct node{int add, next, val, pre, tag;
}E[N];
bool cmp(node a, node b){return a.tag < b.tag; 
} int main(){int p1, p2, n, add;cin>>p1>>p2>>n;for(int i = 0; i < N; i++){E[i].tag = 0x3f3f3f3f; }for(int i = 0; i < n; i ++){cin>>add;E[add].add = add;cin>>E[add].val>> E[add].next;}int q1 = p1, q2 = p2;int cnt1= 0, cnt2 = 0;stack<int> st1, st2;while(q1 != -1){st1.push(q1);cnt1++;q1 = E[q1].next;}while(q2 != -1){cnt2++;st2.push(q2);q2 = E[q2].next;}if(cnt1 > cnt2){ //短的反向合并 L1长 L2短 q1 =  p1;int u = 1, v = 0; while(q1 != -1){E[q1].tag = u + v; if(u % 2 ==0 && u != 0){if(st2.size()){int uu = st2.top();v++; E[uu].tag = u+v;st2.pop();   } } u++; q1= E[q1].next; } }else{ //L2长 L1短 q2 =  p2;int u = 1, v = 0; while(q2 != -1){E[q2].tag = u + v; if(u % 2 ==0 && u != 0){if(st1.size()){int uu = st1.top();v++; E[uu].tag = u+v;st1.pop();   } }u++; q2= E[q2].next; } }sort(E, E+N, cmp); for(int i = 0; i < cnt1+cnt2; i++){printf("%05d %d ",E[i].add, E[i].val);if(i != cnt1+cnt2 - 1) printf("%05d\n", E[i+1].add);else printf("-1\n"); } return 0;
}

这篇关于7-2 Merging Linked Lists (25 分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---