Given two singly linked lists L1?=a1?→a2?→?→an?1?→an? and L2?=b1?→b2?→?→bm?1?→bm?. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a1?→a2?→bm?→a3?→a4?→bm?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.
Input Specification:
Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L1? and L2?, plus a positive N (≤105) 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 105, 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題目大意：給定兩個單鏈表L1 = a1 → a2 → … → an-1 → an，和L2 = b1 → b2 → … → bm-1 → bm，將較短的那個鏈表逆序，然后將之并入比較長的那個鏈表，得到一個形如a1 → a2 → bm → a3 → a4 → bm-1 … 的結果，例如給定兩個鏈表分別為6→7和1→2→3→4→5，你應該輸出1→2→7→3→4→6→5。
分析：由于題目沒有說哪個鏈表更長，因此首先要先確定短的鏈表是哪個，再把短的鏈表逆序。之后長的鏈表每前進2步，短的鏈表前進1步。注意有可能n=2*m的邊界條件。
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#define INF 0xffffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;typedef struct node
{int val,next,id;
}node;int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("in.txt","w",stdout);clock_t start=clock();#endif //testint r1,r2,n;scanf("%d%d%d",&r1,&r2,&n);node num[100000];for(int i=0;i<100000;++i)num[i].val=0,num[i].next=-1,num[i].id=i;for(int i=0;i<n;++i){int a,b,c;scanf("%d%d%d",&a,&b,&c);num[a].val=b,num[a].next=c;}int t1=0,t2=0,pos1=r1,pos2=r2;while(pos1!=-1)t1++,pos1=num[pos1].next;while(pos2!=-1)t2++,pos2=num[pos2].next;if(t1<t2)swap(r1,r2);pos1=r1,pos2=r2;int temp=-1,next=-1;while(pos2!=-1){if(num[pos2].next==-1)r2=pos2;next=num[pos2].next,num[pos2].next=temp,temp=pos2,pos2=next;}// pos2=r2;
// while(pos2!=-1)
// {
// printf("%05d %d %05d\n",num[pos2].id,num[pos2].val,num[pos2].next);
// pos2=num[pos2].next;
// }printf("\n");pos2=r2;int t=0;while(pos1!=-1){if(t<2||pos2==-1){if(pos1==r1)printf("%05d %d",num[pos1].id,num[pos1].val);else printf(" %05d\n%05d %d",num[pos1].id,num[pos1].id,num[pos1].val);t++;pos1=num[pos1].next;}else{printf(" %05d\n%05d %d",num[pos2].id,num[pos2].id,num[pos2].val);pos2=num[pos2].next;t=0;}}if(pos2!=-1)printf(" %05d\n%05d %d",num[pos2].id,num[pos2].id,num[pos2].val);pos2=num[pos2].next;t=0;printf(" -1\n");#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s為單位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms為單位#endif //testreturn 0;
}
