PTA-学校-数据结构（链表去重、两个有序链表合并）

2-5 链表去重

分数 5

作者 陈越

单位 浙江大学

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

输入格式：

输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。

随后 N 行，每行按以下格式描述一个结点：

地址 键值 下一个结点

其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。

输出格式：

首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

输入样例：

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

输出样例：

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

解析（还没搞懂）

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXN 100000

typedef struct Node {
    int addr;
    int key;
    struct Node* next;
} ListNode;

// 创建新节点
ListNode* createNode(int addr, int key) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->addr = addr;
    newNode->key = key;
    newNode->next = NULL;
    return newNode;
}

int main() {
    int head_addr, n;
    scanf("%d%d", &head_addr, &n);
    
    // 用数组存储所有节点信息，便于通过地址快速查找
    int keys[MAXN] = {0};
    int nexts[MAXN] = {0};
    
    for (int i = 0; i < n; i++) {
        int addr, key, next;
        scanf("%d%d%d", &addr, &key, &next);
        keys[addr] = key;
        nexts[addr] = next;
    }
    
    ListNode* kept_head = NULL;    // 保留链表的头节点
    ListNode* kept_tail = NULL;    // 保留链表的尾节点
    ListNode* removed_head = NULL; // 删除链表的头节点
    ListNode* removed_tail = NULL; // 删除链表的尾节点
    
    int appeared[10001] = {0}; // 记录绝对值是否出现过
    
    int current_addr = head_addr;
    
    // 遍历原链表
    while (current_addr != -1) {
        int key = keys[current_addr];
        int abs_key = abs(key);
        
        ListNode* newNode = createNode(current_addr, key);
        
        if (!appeared[abs_key]) {
            // 第一次出现这个绝对值，加入保留链表
            appeared[abs_key] = 1;
            
            if (kept_head == NULL) {
                kept_head = kept_tail = newNode;
            } else {
                kept_tail->next = newNode;
                kept_tail = newNode;
            }
        } else {
            // 重复出现，加入删除链表
            if (removed_head == NULL) {
                removed_head = removed_tail = newNode;
            } else {
                removed_tail->next = newNode;
                removed_tail = newNode;
            }
        }
        
        current_addr = nexts[current_addr];
    }
    
    // 输出保留链表
    ListNode* current = kept_head;
    while (current != NULL) {
        if (current->next != NULL) {
            printf("%05d %d %05d\n", current->addr, current->key, current->next->addr);
        } else {
            printf("%05d %d -1\n", current->addr, current->key);
        }
        current = current->next;
    }
    
    // 输出删除链表
    current = removed_head;
    while (current != NULL) {
        if (current->next != NULL) {
            printf("%05d %d %05d\n", current->addr, current->key, current->next->addr);
        } else {
            printf("%05d %d -1\n", current->addr, current->key);
        }
        current = current->next;
    }
    
    // 释放链表内存
    current = kept_head;
    while (current != NULL) {
        ListNode* temp = current;
        current = current->next;
        free(temp);
    }
    
    current = removed_head;
    while (current != NULL) {
        ListNode* temp = current;
        current = current->next;
        free(temp);
    }
    
    return 0;
}

2-6 两个有序链表合并（新表不含重复元素）

分数 4

作者 陈晓梅

单位 广东外语外贸大学

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
要求S3中没有重复元素。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，要求链表中没有重复元素。数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

在这里给出一组输入。例如：

1 3 3 5 8 -1
2 3 4 6 8 10 -1

输出样例:

在这里给出相应的输出。例如：

1 2 3 4 5 6 8 10

解析

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

int main() {
    LNode *L1_head = (LNode*)malloc(sizeof(LNode));
    LNode *L2_head = (LNode*)malloc(sizeof(LNode));
    L1_head->next = NULL;
    L2_head->next = NULL;
    LNode *L1_tail = L1_head;
    LNode *L2_tail = L2_head;

    int n = 0;

    while (scanf("%d", &n) == 1 && n != -1) {
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->next = NULL;
        newNode->data = n;
        L1_tail->next = newNode;
        L1_tail = newNode;
    }


    while (scanf("%d", &n) == 1 && n != -1) {
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->next = NULL;
        newNode->data = n;
        L2_tail->next = newNode;
        L2_tail = newNode;
    }


    LNode *L3_head = (LNode*)malloc(sizeof(LNode));
    L3_head->next = NULL;
    LNode *L3_tail = L3_head;

    LNode *p1 = L1_head->next;
    LNode *p2 = L2_head->next;


    while (p1 != NULL && p2 != NULL) {
        if (p1->data == p2->data) {
            // 情况1：S1和S2当前元素相同（去重，只插一次）
            LNode *newNode = (LNode*)malloc(sizeof(LNode));
            newNode->data = p1->data;
            newNode->next = NULL;
            L3_tail->next = newNode;
            L3_tail = newNode;

            // 跳过S1中与当前元素重复的节点
            while (p1 != NULL && p1->data == newNode->data) {
                p1 = p1->next;
            }
            // 跳过S2中与当前元素重复的节点
            while (p2 != NULL && p2->data == newNode->data) {
                p2 = p2->next;
            }
        } else if (p1->data < p2->data) {
            // 情况2：S1当前元素更小（插入后跳过S1内部重复）
            LNode *newNode = (LNode*)malloc(sizeof(LNode));
            newNode->data = p1->data;
            newNode->next = NULL;
            L3_tail->next = newNode;
            L3_tail = newNode;

            // 跳过S1中与当前元素重复的节点
            while (p1 != NULL && p1->data == newNode->data) {
                p1 = p1->next;
            }
        } else {
            // 情况3：S2当前元素更小（插入后跳过S2内部重复）
            LNode *newNode = (LNode*)malloc(sizeof(LNode));
            newNode->data = p2->data;
            newNode->next = NULL;
            L3_tail->next = newNode;
            L3_tail = newNode;

            // 跳过S2中与当前元素重复的节点
            while (p2 != NULL && p2->data == newNode->data) {
                p2 = p2->next;
            }
        }
    }

    // 6. 处理剩余节点（p1或p2的剩余部分，需去重后插入）
    // 处理p1剩余节点
    while (p1 != NULL) {
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = p1->data;
        newNode->next = NULL;
        L3_tail->next = newNode;
        L3_tail = newNode;

        // 跳过p1中与当前元素重复的节点
        while (p1 != NULL && p1->data == newNode->data) {
            p1 = p1->next;
        }
    }
    // 处理p2剩余节点
    while (p2 != NULL) {
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = p2->data;
        newNode->next = NULL;
        L3_tail->next = newNode;
        L3_tail = newNode;

        // 跳过p2中与当前元素重复的节点
        while (p2 != NULL && p2->data == newNode->data) {
            p2 = p2->next;
        }
    }

    LNode *p3 = L3_head->next;
    int flag = 1;
    if (p3 == NULL) {
        printf("NULL");
    } else {
        while (p3 != NULL) {
            if (flag == 1) {
                printf("%d", p3->data);
                flag = 0;
            } else {
                printf(" %d", p3->data);
            }
            p3 = p3->next;
        }
    }
    return 0;
}

注意

1.题中说新链表不能有重复的，所以在插入新链表时要注意跳过重复的。

while (p1 != NULL && p1->data == newNode->data) {
       p1 = p1->next;
}

2.尾插法要一个tail指针，不能用头指针，不然会失去头指针的地址。