关于算法-数据结构:PAT甲级2019年秋季考试-72-Merging-Linked-Lists

7-2 Merging Linked Lists (25 分)

Given two singly linked lists L​1​​=$a​_1$​​→$a​_2$→⋯→$a​_{n-1}$​​→$a​_n$​​ and L​2​​=$b​_1​​$→$b​_2$​​→⋯→$b​_{m-1}$​​→$b​_m​​$​​. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a​1​​→a​2​​→b​m​​→a​3​​→a​4​​→b​m−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 L​1​​ and L​2​​, 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 10​5​​, 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

题目限度：

题目粗心：

给定两个链表，当初须要将短的链表依照如下的办法插入到长的链表中，首先将短链表逆序，而后每隔两个节点插入到长的链表中去。

算法思路：

咱们应用 list1 和 list2 别离保留两个链表，这里假如 list1 保留的是短的，另外一种状况一样，应用 result 保留所有插入结束的链表，其实能够分 2 种情景思考这个问题，第一种就是 list1 还有节点须要插入，那么就把插入 2 个 list2 节点和 1 个 list1 节点看成一个原子操作，第二种状况就是 list1 没有节点插入了，那么就顺次插入 list2 节点，直到结束即可。具体做法如下：

• 1、应用 index_list1 = list1.size()-1，index_list2 = 0，别离示意目前 list1 和 list2 的待插入地位
• 2、只有 index_list2<list2.size()，就阐明插入过程没有完结转 3，否则转 5
• 3、如果 index_list1>=0，阐明 list1 还有节点，插入 2 个 list2 节点和 1 个 list1 节点，转 2
• 4、如果 index_list1<0, 直接插入 list2 节点，转 2
• 5、输入所有的 result，每一个节点的 next 即为后一节点的 address。

提交后果：

AC 代码：

#include<cstdio>
#include<vector>

using namespace std;

struct Node{
    int address;
    int data;
    int next;
}all[100000];
int num = 0;

vector<Node> list1;
vector<Node> list2;
vector<Node> result;

int main(){
    int begin1,begin2,N;
    scanf("%d %d %d",&begin1,&begin2,&N);
    Node node;
    for(int i=0;i<N;++i){scanf("%d %d %d",&node.address,&node.data,&node.next);
        all[node.address] = node;
    }
    while(begin1!=-1){list1.push_back(all[begin1]);
        begin1 = all[begin1].next;
    }
    while(begin2!=-1){list2.push_back(all[begin2]);
        begin2 = all[begin2].next;
    }
    if(list1.size()<list2.size()){
        // list2 更长
        int index_list1 = list1.size()-1;
        int index_list2 = 0;
        while(index_list2<list2.size()){if(index_list1>=0){
                // 如果 list1 还有节点
                for(int i=0;i<2;++i){result.push_back(list2[index_list2]);
                    ++index_list2;
                }
                result.push_back(list1[index_list1]);
                --index_list1;
            }else{result.push_back(list2[index_list2]);
                ++index_list2;
            }
        }
    }else{
        // list1 更长
        int index_list1 = 0;
        int index_list2 = list2.size()-1;
        while(index_list1<list1.size()){if(index_list2>=0){
                // 如果 list2 还有节点
                for(int i=0;i<2;++i){result.push_back(list1[index_list1]);
                    ++index_list1;
                }
                result.push_back(list2[index_list2]);
                --index_list2;
            }else{result.push_back(list1[index_list1]);
                ++index_list1;
            }
        }
    }
    for(int i=0;i<result.size();++i){printf("%05d %d",result[i].address,result[i].data);
        if(i!=result.size()-1){printf("%05d\n",result[i+1].address);
        }else{printf("-1\n");
        }
    }
    return 0;
}