第13章 链表

1032. Sharing

笔记

• 用静态链表存储两个字符串，然后遍历第一个字符串，并把地址存入哈希表中，然后再遍历第二个字符串，同时查找哈希表，如果哈希表存在则返回该结点，否则返回-1
• 用哈希表优化后，时间复杂度变成$O(n+m)$
• 注意地址包含前导零，因此需要用%05d输出

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
char e[N];
int ne[N];
int start1, start2, n;
bool h[N];      // 哈希表

int main() {
    scanf("%d%d%d", &start1, &start2, &n);
    int address, next_address;
    char data;

    while(n--) {
        scanf("%d %c %d", &address, &data, &next_address);
        e[address] = data;
        ne[address] = next_address;
    }

    for (int p = start1; ~p; p = ne[p])
        h[p] = true;

    for (int p = start2; ~p; p = ne[p])
        if (h[p]) {
            printf("%05d\n", p);
            return 0;
        }

    puts("-1");
    return 0;
}

1074. Reversing Linked List

笔记

• 用静态数组保存链表，然后把链表数据按顺序拷贝到vector<int>中，在vector中实现翻转，再输出结果
• 为了不让不足k个的元素翻转，可让for的循环条件改为i + k - 1 < a.size()
• 注意地址包含前导零，因此需要用%05d输出

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int h, e[N], ne[N];
vector<int> a;

int main() {
    scanf("%d%d%d", &h, &n, &k);

    int address, data, next_address;
    while(n--) {
        scanf("%d%d%d", &address, &data, &next_address);
        e[address] = data;
        ne[address] = next_address;
    }

    for (int p = h; ~p; p = ne[p])
        a.push_back(p);

    for (int i = 0; i + k - 1 < a.size(); i += k)
        reverse(a.begin() + i, a.begin() + i + k);

    for (int i = 0; i < a.size(); i++) {
        address = a[i];
        data = e[address];
        printf("%05d %d ", address, data);
        if (i == a.size() - 1)
            printf("%d\n", -1);
        else
            printf("%05d\n", a[i + 1]);

    }

    return 0;
}

1097. Deduplication on a Linked List

笔记

• 类似“Reversing Linked List”的做法。首先用静态链表存储链表，然后不删除的元素依次放入vector<int> a，删除的元素依次放入vector<int> b，最后输出即可
• 注意地址包含前导零，用%05d格式化输出

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N = 1e5 + 10, M = 1e4 + 10;
int n, h, e[N], ne[N];
bool st[M];      // 哈希表
vector<int> a, b;

void print(vector<int>& q) {
    int address, data, next_address;
    for (int i = 0; i < q.size(); i++) {
        address = q[i];
        data = e[address];
        printf("%05d %d ", address, data);
        if (i + 1 == q.size()) printf("-1\n");
        else printf("%05d\n", q[i + 1]);
    }
}

int main() {
    scanf("%d%d", &h, &n);
    int address, data, next_address;
    while(n--) {
        scanf("%d%d%d", &address, &data, &next_address);
        e[address] = data;
        ne[address] = next_address;
    }

    for (int p = h; ~p; p = ne[p]) {
        int t = abs(e[p]);
        if (st[t]) b.push_back(p);
        else{
            a.push_back(p);
            st[t] = true;
        }
    }

    print(a);
    print(b);

    return 0;
}

1133. Splitting A Linked List

笔记

• 题意为：把链表元素按要求分成3段，且每段元素的相对次序与原链表次序一致

  • $x < 0$
  • $x \in [0, K]$
  • $x > K$

• 思路：类似“Deduplication on a Linked List”的做法，首先用静态链表存储链表，然后把三种关系的元素分别依次放入vector<int> a, b, c中，最后连接a、b和c，然后输出即可

• vector<int>的连接方法：在a末尾插入b可用a.insert(a.end(), b.begin(), b.end())

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n, k, h, e[N], ne[N];
vector<int> a, b, c;

int main() {
    scanf("%d%d%d", &h, &n, &k);

    int address, data, next_address;
    while(n--) {
        scanf("%d%d%d", &address, &data, &next_address);
        e[address] = data;
        ne[address] = next_address;
    }

    for (int p = h; ~p; p = ne[p])
        if (e[p] < 0) a.push_back(p);
        else if (e[p] > k) c.push_back(p);
        else b.push_back(p);

    a.insert(a.end(), b.begin(), b.end());
    a.insert(a.end(), c.begin(), c.end());

    for (int i = 0; i < a.size(); i++) {
        address = a[i];
        data = e[address];
        printf("%05d %d ", address, data);
        if (i + 1 == a.size()) printf("-1\n");
        else printf("%05d\n", a[i + 1]);
    }

    return 0;
}