PAT 1161 Merging Linked Lists

原题链接:暂无
关键词:链表

Given two singly linked lists L 1 =a 1 →a 2 →…→a n−1 →a n L1=a1→a2→…→an−1→an and L 2 =b 1 →b 2 →…→b m−1 →b m L2=b1→b2→…→bm−1→bm . If n≥2m 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 … 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 L 1 L1 and L 2 L2 , plus a positive N(≤10 5 ) 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 10 5 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

题目大意: 给出两个链表,要求按照规则输出合并后的链表
思路: 先把节点数据存储下来,然后分别获取出两条链表的节点,然后进行按要求拼接。
代码:

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

const int N = 100000 + 10; 
struct Node
{
    int address, data, next;
}nodes[N];

int main()
{
    int head, add1, add2, n;
    cin >> add1 >> add2 >> n;	//2个开始地址 结点数 
    vector<Node>v1, v2, res;	//存储链表值
    for (int i = 0; i < n; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        nodes[address] = { a,b,c };
    }
    
    for (int p = add1; p != -1; p = nodes[p].next)
        v1.push_back(nodes[p]);
    for (int p = add2; p != -1; p = nodes[p].next)
        v2.push_back(nodes[p]);
        
    if (v1.size() > v2.size())
        head = add1;
    else
    {
        v2 = v1;	//v2是短链表 
        head = head2;
    }
    
    int k = 0;
    while (head != -1)
    {
        res.push_back(nodes[head]);
        ++k;
        if (k % 2 == 0 && !v2.empty())//两个中间插一个
        {
            res.push_back(v2.back());
            v2.pop_back();
        }
        head = nodes[head].next;
    }
    
    for (int i = 0; i < res.size() - 1; ++i)
        printf("%05d %d %05d\n", res[i].addr, res[i].val, res[i+1].addr);
    printf("%05d %d %d\n", res.back().addr, res.back().val, -1);
    return 0;
}

热门文章

暂无图片
编程学习 ·

Qt QTreeWidget的级联选中

在使用QTreeWidget显示文件树时,需要对树的节点做一些功能的限制:勾选某一节点时,该节点的子项自动全部选中 子项部分勾选时,父节点状态为部分勾选 子项全部勾选时,父节点自动设置勾选首先,查看了Qt文档,发现竟然没有提供这个功能,所以自己写了一个简单的例子。 先看效…
暂无图片
编程学习 ·

命令模式

菜鸟教程中代理模式总结)1.定义:将请求以命令的形式包裹在对象中,并传给调用对象。调用对象寻找可以处理该命令 的合适的对象,并把该命令传给相应的对象,该对象执行命令。 2.主要解决:行为请求者与行为实现者通常是一种紧耦合的关系,为了消除这种耦合关系 3.何时使用:命…
暂无图片
编程学习 ·

深度学习在美团推荐平台排序中的运用

美团作为国内最大的生活服务平台,业务种类涉及食、住、行、玩、乐等领域,致力于让大家吃得更好,活得更好,有数亿用户以及丰富的用户行为。随着业务的飞速发展,美团的用户和商户数在快速增长。在这样的背景下,通过对推荐算法的优化,可以更好的给用户提供感兴趣的内容,帮…
暂无图片
编程学习 ·

MapReduce详细分析

一、MapReduce概述 1、定义 MapReduce核心功能是将用户编写的业务逻辑代码和自带默认组件整合成一个完整的分布式运算程序,并发运行在一个Hadoop集群 上。 2、MR进程 一个完整的MapR educe程序在分布式运行时有三类实例进程:**Mr AppMaster:**负责整个程序的过程调度及状态协调…
暂无图片
中恒嘉业 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
cgfy ·

8. 源码分析之ConsumeQueue

源码分析之ConsumeQueue 消息发送时数据在ConsumeQueue的落地 ​ 连续发送5条消息&#xff0c;消息是不定长&#xff0c;首先所有信息先放入 Commitlog中&#xff0c;每一条消息放入Commitlog的时候都需要上锁&#xff0c;确保顺序的写入。 ​ 当Commitlog写成功了之后。数据…
暂无图片
coreui ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
coreui ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
未来博客 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
未来博客 ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
建站日记 ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
建站日记 ·

STL Practice —— 【map (1)】

Description 给出学生姓名和分数&#xff0c;要求你输入姓名查询分数。 Input 输入包含T组测试数据。 开头是一个正整数T (0<T<10)&#xff0c;为测试数据数量。 对于每组测试数据&#xff0c;第一行是一个正整数N (0<N<100000)。 接下来有N行&#xff0c;每行包…
暂无图片
mfbz ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
mfbz ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
珊珊日记 ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
珊珊日记 ·

8. 源码分析之ConsumeQueue

源码分析之ConsumeQueue 消息发送时数据在ConsumeQueue的落地 ​ 连续发送5条消息&#xff0c;消息是不定长&#xff0c;首先所有信息先放入 Commitlog中&#xff0c;每一条消息放入Commitlog的时候都需要上锁&#xff0c;确保顺序的写入。 ​ 当Commitlog写成功了之后。数据…