526互联

PAT Basic 1105. 链表合并

发布时间 2023-04-17 20:06:25作者: 十豆加日月

PAT Basic 1105. 链表合并

1. 题目描述：

给定两个单链表 \(L_1=a_1→a_2→⋯→a_{n−1}→a_n\) 和 \(L_2=b_1→b_2→⋯→b_{m−1}→b_m\)。如果 \(n≥2m\)，你的任务是将比较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如 \(a_1→a_2→b_m→a_3→a_4→b_{m−1}⋯\) 的结果。例如给定两个链表分别为 \(6→7\) 和 \(1→2→3→4→5\)，你应该输出 \(1→2→7→3→4→6→5\)。

2. 输入格式：

输入首先在第一行中给出两个链表 \(L_1\) 和 \(L_2\) 的头结点的地址，以及正整数 \(N\) (\(≤10^5\))，即给定的结点总数。一个结点的地址是一个 5 位数的非负整数，空地址 NULL 用 -1 表示。

随后 \(N\) 行，每行按以下格式给出一个结点的信息：

Address Data Next

其中 Address 是结点的地址，Data 是不超过 \(10^5\) 的正整数，Next 是下一个结点的地址。题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。

3. 输出格式：

按顺序输出结果链表，每个结点占一行，格式与输入相同。

4. 输入样例：

00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1

5. 输出样例：

01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

根据题意先将所有的结点进行存储，然后分别根据链表 \(L_1\) 和 \(L_2\) 的头结点地址构造两个链表，最后涉及到逆转链表和合并链表。为了节省时间，解决这类题目都是将链表进行顺序存储，可以直接寻址。定义结构体Node存储结点相关信息，根据地址最大值定义结构体数组顺序存储结点，这里结点地址是5位非负整数，地址最大值即为 \(10^5\)。定义List[MAX_ADDRESS]存储所有结点，List1[MAX_ADDRESS]存储链表\(L_1\)，List2[MAX_ADDRESS]存储链表\(L_2\)，ListRes[MAX_ADDRESS]存储最终合并的链表，先将较长链表插入ListRes，每隔2个元素留出1个空白位置，直到留出较短链表长度个空白位置为止，较长链表插入完后将较短链表逆序插入到相应空白位置即可。需要注意的地方有：

  • 题目未保证输入链表 \(L_1\) 的长度一定大于 \(L_2\)，需要自己判断，分两种情况进行处理。
  • 将较短链表逆序插入到较长链表时，要留出较短链表对应长度个空白位置，这里定义vacancyCount维护空白位置的个数。

第一次提交时testpoint3报wrong answer，检查后发现vacancyCount的判断条件写错了，将<=改为<后通过testpoint3，相关的代码即if(vacancyCount < list2Len)和if(vacancyCount < list1Len)。

My Code:

#include <stdio.h>

#define MAX_ADDRESS 100000

typedef struct node
{
    int address;
    int data;
    int next;
} Node;

// first submit testpoint3 wrong answer
int main(void)
{
    int pLink1=0, pLink2=0, nodeCount=0;
    Node List[MAX_ADDRESS];
    int tempAdr=0, tempData=0, tempNext=0;
    int pTemp=0; // iterator of linkList
    int list1Len=0, list2Len=0;
    Node List1[MAX_ADDRESS], List2[MAX_ADDRESS];
    Node ListRes[MAX_ADDRESS];
//     int pRes=0; // head address of res
    int insertFlag=0;
    int insertIndex=0;
    int vacancyCount=0;
    
    scanf("%d%d%d", &pLink1, &pLink2, &nodeCount);
    for(int i=0; i<nodeCount; ++i)
    {
        scanf("%d%d%d", &tempAdr, &tempData, &tempNext);
        
        List[tempAdr].address = tempAdr;
        List[tempAdr].data = tempData;
        List[tempAdr].next = tempNext;
    }
    
    pTemp = pLink1;
    while(pTemp != -1) // calculate link1 length & assign List1
    {
        List1[list1Len++] = List[pTemp];
        pTemp = List[pTemp].next;
    }
    pTemp = pLink2;
    while(pTemp != -1) // calculate link2 length & assign List2
    {
        List2[list2Len++] = List[pTemp];
        pTemp = List[pTemp].next;
    }
    //printf("Len1: %d Len2: %d\n", list1Len, list2Len);
    
    if(list1Len > list2Len) // reverse the link2
    {
//         pRes = pLink1; // set head address
        insertIndex = 0;
        for(int i=0; i<list1Len; ++i) // insert list1
        {
            ListRes[insertIndex++] = List1[i];
            ++insertFlag;
            if(insertFlag == 2)
            {
                if(vacancyCount < list2Len) // here recitfy <= to <, fixed testpoint3
                {
                    ++vacancyCount; // count vacancy
                    ++insertIndex;
                }
                insertFlag = 0;
            }
        }
        
        insertIndex = 2; // the question assure at least 1 node
        for(int i=list2Len-1; i>=0; --i) // insert list2
        {
            ListRes[insertIndex] = List2[i];
            insertIndex += 3;
        }
        
    }
    else // reverse the link1
    {
//         pRes = pLink2; // set head address
        insertIndex = 0;
        for(int i=0; i<list2Len; ++i) // insert list2
        {
            ListRes[insertIndex++] = List2[i];
            ++insertFlag;
            if(insertFlag == 2)
            {
                if(vacancyCount < list1Len) // here recitfy <= to <, fixed testpoint3
                {
                    ++vacancyCount; // count vacancy
                    ++insertIndex;
                }
                insertFlag = 0;
            }
        }
        
        insertIndex = 2; // the question assure at least 1 node
        for(int i=list1Len-1; i>=0; --i) // insert list2
        {
            ListRes[insertIndex] = List1[i];
            insertIndex += 3;
        }
    }
    
    for(int i=0; i<list1Len+list2Len-1; ++i) // outout except last node
    {
        printf("%05d %d %05d\n", ListRes[i].address, ListRes[i].data, ListRes[i+1].address);
    }
    printf("%05d %d -1\n", ListRes[list1Len+list2Len-1].address, ListRes[list1Len+list2Len-1].data);
    
    
//     for(int i=0; i<list1Len; ++i)
//     {
//         printf("%d\n", List1[i].data);
//     }
//     for(int i=0; i<list2Len; ++i)
//     {
//         printf("%d\n", List2[i].data);
//     }
    
    
    return 0;
}