重返天梯-链表问题

链表问题通用解题模板

结构体存储

struct Node {
	// 地址，数据，下一结点地址
    int addr, data, ne;
}node[N];
1
2
3
4

根据起始结点及对应后续还原链表

for (int i = sta; i != -1; i = node[i].ne) 
        v.push_back(node[i]);
1
2

重返天梯-L2-002 链表去重 (25 分)

题目描述

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

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Node {
    int addr, data, ne;
}node[N];
bool st[N];
int sta, n;
vector<Node> v, ans1, ans2;

int main() {
    cin >> sta >> n;
    
    for (int i = 0; i < n; i++) {
        int addr, data, ne;
        cin >> addr >> data >> ne;
        node[addr] = {addr, data, ne};
    }
    
    for (int i = sta; i != -1; i = node[i].ne) 
        v.push_back(node[i]);
    
    for (int i = 0; i < v.size(); i++) {
        int dat = abs(v[i].data);
        if (!st[dat]) {
            ans1.push_back(v[i]);
            st[dat] = true;
        } else {
            ans2.push_back(v[i]);
        }
    }
    
    for (int i = 0; i < ans1.size(); i++) {
        if (i != ans1.size()-1)
            printf("%05d %d %05d\n", ans1[i].addr, ans1[i].data, ans1[i+1].addr);
        else
            printf("%05d %d -1\n", ans1[i].addr, ans1[i].data);
    }
    
    for (int i = 0; i < ans2.size(); i++) {
        if (i != ans2.size()-1)
            printf("%05d %d %05d\n", ans2[i].addr, ans2[i].data, ans2[i+1].addr);
        else
            printf("%05d %d -1\n", ans2[i].addr, ans2[i].data);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

重返天梯-L2-022 重排链表 (25 分)

题目描述

L2-022 重排链表 (25 分)原题链接
给定一个单链表 $L1\to L2\to \cdots \to Ln-1\to Ln$​ ，请编写程序将链表重新排列为 $Ln\to L1\to Ln-1\to L2\to \cdots$。例如：给定L为$1\to 2\to 3\to 4\to 5\to 6$，则输出应该为$6\to 1\to 5\to 2\to 4\to 3$。

这道题先把所有的数据存储下来，然后再利用头结点进行遍历，按顺序再重新存储一遍结点。
尾头依次放入答案中的数组，用的是双指针算法
通过计算得出规律，当l-r=1时，所以结点按题目要求存放完毕

C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Node {
    int addr, data, ne;
}node[N];
int n, sta;
vector<Node> v, ans;

int main() {
    cin >> sta >> n;
    
    for (int i = 0; i < n; i++) {
        int addr, data, ne;
        cin >> addr >> data >> ne;
        node[addr] = {addr, data, ne};
    }
    
    for (int i = sta; i != -1; i = node[i].ne) 
        v.push_back(node[i]);
    
    int l = 0, r = v.size()-1;
    while (true) {
        ans.push_back(v[r]);
        r--;
        if (l - r == 1) break;
        ans.push_back(v[l]);
        l++;
        if (l - r == 1) break;
    }
    
    for (int i = 0; i < ans.size(); i++) {
        if (i != ans.size() - 1)
            printf("%05d %d %05d\n", ans[i].addr, ans[i].data, ans[i+1].addr);
        else 
            printf("%05d %d -1\n", ans[i].addr, ans[i].data);
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40