[PAT解题报告] Deduplication on a Linked List
PAT的链表题,表示链表的方法很诡异,类似的表示还有1052, 1074。也不难,本题给定一个存储整数的链表,只保存每种绝对值第一次出现的节点,同一个绝对值第二次及以后的出现都扔掉,保留的节点和扔掉的节点分别组成两个小链表。
链表存放整数的绝对值不超过10000,所以可以用bool数组或者bitmap保存某个绝对值在之前是否出现过。
不知道有没有极端情况,输入的链表就是个空的……
总之,我们可以先新建立两个表头h1, h2 和表尾t1, t2,初始都是空的,表示我们最后保留的链表和过滤掉的链表。链表的优势就是对每个节点可以单独折腾……
我们对原始链表里每个节点,可以通过我们那个bool数组判断这个绝对值是否出现过,如果出现过就接到第二个链表末尾,否则就放到第一个链表的末尾。接在链表末尾的操作注意和用指针差不多,注意是否是第一个表头节点,同时别忘更新最后一个元素的地址,因为每次都要接在最后一个元素后面……当然接在前面再翻转一次也是可以的。
最后输出也要注意链表为空的情况,还有注意最后一个位置的next是-1。
难度不大,就是每种细节的处理而已。

代码:
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

int Next[1000000];
int a[1000000];
bool mark[10005];

int main() {
int n;
int head;
    for (scanf("%d%d",&head,&n);n;--n) {
        int x;
        scanf("%d",&x);
        scanf("%d%d",a + x, Next + x);
    }
    int h1 = -1, h2 = -1, t1 = -1, t2 = -1;
    for (; head >= 0; head = Next[head]) {
        int x = (a[head] >= 0)?a[head]:(-a[head]);
        if (mark[x]) {
            if (t2 < 0) {
                h2 = t2 = head;
            }
            else {
                t2 = Next[t2] = head;
            }
        }
        else {
            mark[x] = true;
            if (t1 < 0) {
                h1 = t1 = head;
            }
            else {
                t1 = Next[t1] = head;
            }
        }
    }
    if (t1 >= 0) {
        Next[t1] = -1;
        for (head = h1; head >= 0; head = Next[head]) {
            printf("%05d %d", head, a[head]);
            if (Next[head] >= 0) {
                printf(" %05d\n", Next[head]);
            }
            else {
                puts(" -1");
            }
        }
    }
    if (t2 >= 0) {
        Next[t2] = -1;
        for (head = h2; head >= 0; head = Next[head]) {
            printf("%05d %d", head, a[head]);
            if (Next[head] >= 0) {
                printf(" %05d\n", Next[head]);
            }
            else {
                puts(" -1");
            }
        }
    }
            
    return 0;
}


原题链接: http://www.patest.cn/contests/pat-a-practise/1097

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 14:39
门头沟学院_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议