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

本文链接：https://blog.csdn.net/allisonshing/article/details/100642844

本文介绍了一道PAT甲级考试中的链表题目，要求将两个已知长度的链表按特定规则合并。文章提供了两种解题方法，包括使用排序的优化方案，并给出了详细的代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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 00