2019年9月8日秋季PAT甲级题解-2-1161-Merging Linked Lists (25 分) 双解法

青旅半醒 2024-04-18 15:28 28阅读 0赞

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 (≤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 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

--------------------

# 分析 #

属于甲级常考的静态链表题目。如果想了解静态链表题的思路可以先去看晴神宝典。

第一种写法就是晴神宝典的写法，用排序，只用一个vector，并且会修改到新链表的next项。

第二种写法就是参考[1133柳神的写法][1133]，不同排序，用多个vector，不用修改next项。

第三种写法是第二种写法的优化（大家直接看她的就可以了）：[https://blog.csdn.net/Exupery\_/article/details/100698828][https_blog.csdn.net_Exupery_article_details_100698828]

--------------------

# 满分代码（方法一）  #

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <set>
    #include <map>
    #include <cmath>
    using namespace std;
    int k, n,m,a,b,c,d,e,ar=1,br=1;
    int ad[100005];
    struct node{
        int addr,data,next,rank;
        bool f=false;
    };
    vector<node> v;
    bool cmp(node &a,node &b){
        if(a.f!=b.f)return a.f>b.f;
        else return a.rank<b.rank;
    }
    int main() {
        scanf("%d %d %d", &a,&b,&n);
        v.resize(n);
        for(int i=0;i<n;i++){
            scanf("%d %d %d",&c,&d,&e);
            ad[c]=i;
            v[i].addr=c;
            v[i].data=d;
            v[i].next=e;
        }
        int as=a,bs=b;
        while(as!=-1){
            v[ad[as]].rank=ar;
            v[ad[as]].f=true;
            as=v[ad[as]].next;
            ar++;
        }
        br=ar;
        while(bs!=-1){
            v[ad[bs]].rank=br;
            v[ad[bs]].f=true;
            bs=v[ad[bs]].next;
            br++;
        }
        ar--;br--;
        if(ar<br-ar){
            as=b;
            bs=a;
            ar=1;
            while(as!=-1){
                v[ad[as]].rank=ar;
                v[ad[as]].f=true;
                as=v[ad[as]].next;
                ar++;
            }
            br=ar;
            while(bs!=-1){
                v[ad[bs]].rank=br;
                v[ad[bs]].f=true;
                bs=v[ad[bs]].next;
                br++;
            }
            ar--;br--;
        }
        sort(v.begin(),v.end(),cmp);
        for(int i=0;i<br;i++){
            if(i>1 && i<ar){
                v[i].rank+=i/2;
            }else if(i>=ar){
                v[i].rank=(br-i)*3;
            }
        }
        sort(v.begin(),v.end(),cmp);
        int bl=br-ar;
        for(int i=0;i<br;i++){
            if(bl>0 && i>0 && (i+1)%3==0){
                int t=v[i-1].next;
                v[i-1].next=v[i].addr;
                v[i].next=t;
                bl--;
            }
        }
        for(int i=0;i<br;i++){
            if(i==br-1) printf("%05d %d -1",v[i].addr,v[i].data);
            else printf("%05d %d %05d\n",v[i].addr,v[i].data,v[i].next);
        }
        return 0;
    }

--------------------

# 满分代码（方法二） #

#include<iostream>
    #include<vector>
    using namespace std;
    struct node{
        int id,data,next;
    };
    node a[100005];
    int main(){
        int ba,bb,n,s,d,e;
        scanf("%d %d %d\n",&ba,&bb,&n);
        vector<node> va,vb,ans;
        for(int i=0;i<n;i++){
            scanf("%d %d %d\n",&s,&d,&e);
            a[s]={s,d,e};
        }
        for(;ba!=-1;ba=a[ba].next){
            va.push_back(a[ba]);
        }
        for(;bb!=-1;bb=a[bb].next){
            vb.push_back(a[bb]);
        }
        if(va.size()>vb.size()){
            int j=(int)vb.size()-1;
            for(int i=0;i<va.size();i++){
                if(i>0 && i%2==0 && j>=0){
                    ans.push_back(vb[j]);
                    j--;
                }
                ans.push_back(va[i]);
                if(i==va.size()-1 && j==0){
                    ans.push_back(vb[j]);
                }
            }
        }else {
            int j=(int)va.size()-1;
            for(int i=0;i<vb.size();i++){
                if(i>0 && i%2==0 && j>=0){
                    ans.push_back(va[j]);
                    j--;
                }
                ans.push_back(vb[i]);
                if(i==vb.size()-1 && j==0){
                    ans.push_back(va[j]);
                }
            }
        }
    
        for(int i=0;i<ans.size();i++){
            if(i!=ans.size()-1)printf("%05d %d %05d\n",ans[i].id,ans[i].data,ans[i+1].id);
            else printf("%05d %d -1",ans[i].id,ans[i].data);
        }
        return 0;
    }

# 更多测试数据集 #

//输入1
    00100 01000 6
    02233 2 34891
    00100 6 00001
    34891 3 10086
    01000 1 02233
    10086 4 -1
    00001 7 -1
    //输出1
    01000 1 02233
    02233 2 00001
    00001 7 34891
    34891 3 10086
    10086 4 00100
    00100 6 -1

//输入2
    00100 01000 8
    02233 2 34891
    00100 7 00001
    34891 3 10086
    01000 1 02233
    00033 5 02342
    10086 4 00033
    00001 8 -1
    02342 6 -1
    //输出2
    01000 1 02233
    02233 2 00001
    00001 8 34891
    34891 3 10086
    10086 4 00100
    00100 7 00033
    00033 5 02342
    02342 6 -1

//输入3
    01000 00033 3
    02233 2 -1
    01000 1 02233
    00033 3 -1
    //输出3
    01000 1 02233
    02233 2 00033
    00033 3 -1

//输入4
    00033 01000 3
    02233 2 -1
    01000 1 02233
    00033 3 -1
    //输出4
    01000 1 02233
    02233 2 00033
    00033 3 -1

//输入6:游离节点不能输出
    02233 01000 6
    02233 2 00033
    01000 1 -1
    00033 3 23421
    23421 4 -1
    27834 9 78932
    78932 8 -1
    //输出6
    02233 2 00033
    00033 3 01000
    01000 1 23421
    23421 4 -1

[1133]: https://www.liuchuo.net/archives/4092
[https_blog.csdn.net_Exupery_article_details_100698828]: https://blog.csdn.net/Exupery_/article/details/100698828