【PAT

文章目录

• 一【题目难度】
• 二【题目编号】
• 三【题目描述】
• 四【题目示例】
• 五【解题思路】
• 六【最终得分】
• 七【代码实现】
• 八【提交结果】

一【题目难度】

• 乙级

二【题目编号】

• 1105 链表合并 (25 分)

三【题目描述】

• 给定两个单链表 L 1 ​ = a 1 ​ → a 2 ​ → ⋯ → a n − 1 ​ → a n L_1​ =a_1​ →a_2​ →⋯→a_{n−1}​ →a_n L1​​=a1​​→a2​​→⋯→an−1​​→an​ 和 L 2 ​ = b 1 ​ → b 2 → ⋯ → b m − 1 ​ → b m L_2​ =b_1​→b_2 →⋯→b_{m−1}​ →b_m L2​​=b1​​→b2​→⋯→bm−1​​→bm​ 。
  

  
  

  如果 n ≥ 2 m n≥2m n≥2m，你的任务是将比较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如 a 1 ​ → a 2 ​ → b m ​ → a 3 → a 4 ​ → b m − 1 ​ ⋯ a_1​ →a_2​ →b_m​ →a_3 →a_4​→b_{m−1}​ ⋯ a1​​→a2​​→bm​​→a3​→a4​​→bm−1​​⋯的结果。
  

  
  

  例如给定两个链表分别为 6 → 7 6→7 6→7 和 1 → 2 → 3 → 4 → 5 1→2→3→4→5 1→2→3→4→5，你应该输出 1 → 2 → 7 → 3 → 4 → 6 → 5 1→2→7→3→4→6→5 1→2→7→3→4→6→5。
  

  
  

四【题目示例】

• 输入格式：
  输入首先在第一行中给出两个链表 L 1 L_1 L1​ 和 L 2 L_2 L2​ 的头结点的地址，以及正整数 N ( ≤ 1 0 5 ) N (≤10^5 ) N(≤105)，即给定的结点总数。
  

  
  

  一个结点的地址是一个 5 5 5 位数的非负整数，空地址 N U L L NULL NULL 用 − 1 -1 −1 表示。
  

  
  

  
  随后 N N N 行，每行按以下格式给出一个结点的信息：
  Address Data Next
  其中 Address 是结点的地址，Data 是不超过 1 0 5 10^5 105 的正整数，Next 是下一个结点的地址。
  

  
  

  题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。
  

  
  

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

  
  

• 输入样例：
  00100 01000 7
  02233 2 34891
  00100 6 00001
  34891 3 10086
  01000 1 02233
  00033 5 -1
  10086 4 00033
  00001 7 -1

• 输出样例：
  01000 1 02233
  02233 2 00001
  00001 7 34891
  34891 3 10086
  10086 4 00100
  00100 6 00033
  00033 5 -1

五【解题思路】

• 不知道为啥，这种题在LeetCode里面做我就没啥问题，就是简单题，在这里就对我来说有点难度了，可能是因为PAT并没有将链表写好吧，看来我的动手能力还需加强啊！总之，这道题目的思路比较好想：只需要扫描输入，计算各个链表长度，然后按照要求输出即可（将短的链表逆序每隔两个插入长的链表）。
  

  
  

  但是 *** 作起来有点难度，需要使用结构体存储每个节点的信息，因为是将短的链表逆序插入，所以需要遍历一遍链表，将其前驱连接。
  

  
  

  其余按照要求输出即可，最后还要注意输出格式，补齐 5 5 5位。
  

  
  

  若不足 5 5 5位补零。
  

  
  

  其中还要注意，结构体要用 s t r u c t struct struct，不要用 t y p e d e f s t r u c t typedef struct typedefstruct，因为前者是变量，后者是类型

六【最终得分】

• 25分

七【代码实现】

#include

struct RES
{
    int data;
    int next;
    int pre;
}res[100000];

void out_1105_LinkedListMerge(int headLong,int rearShort)
{
    int count = 0,p = headLong,q = rearShort,index = 0,ans[100000],flag = 1;
    while(p != -1)
    {
        ans[index++] = p;
        p = res[p].next;
        count++;
        if(count == 2 && q != -1)
        {
            ans[index++] = q;
            q = res[q].pre;
            count = 0;
        }
    }
    for(int i = 0;i<index;i++)
    {
        if(flag > 1)
        {
            printf("%05d\n%05d %d ",ans[i],ans[i],res[ans[i]].data);
        }
        else
        {
            printf("%05d %d ",ans[i],res[ans[i]].data);
            flag++;
        }
    }
    printf("-1");
}

int main()
{
    int l1,l2,n,l1Len = 0,l2Len = 0;
    scanf("%d %d %d",&l1,&l2,&n);
    for(int i = 0;i<n;i++)
    {
        int id;
        scanf("%d",&id);
        scanf("%d %d",&res[id].data,&res[id].next);
    }
    int p1 = l1,pre1 = -1;
    while(p1 != -1)
    {
        res[p1].pre = pre1;
        pre1 = p1;
        p1 = res[p1].next;
        l1Len++;
    }
    int p2 = l2,pre2 = -1;
    while(p2 != -1)
    {
        res[p2].pre = pre2;
        pre2 = p2;
        p2 = res[p2].next;
        l2Len++;
    }
    if(l1Len >= 2 * l2Len)
    {
        out_1105_LinkedListMerge(l1,pre2);
    }
    else if(l2Len >= 2 * l1Len)
    {
        out_1105_LinkedListMerge(l2,pre1);
    }
    return 0;
}

八【提交结果】