avatar

WhitePaper 白芷

Ad Astra Per Aspera.

分类

浏览器扩展

1

Minecraft

1

影视

1

编程

1

算法笔记

2

数据结构

1

设计模式

1

标签

B站

Bilibili

Minecraft

Fabric

字幕

编程

设计模式

Golang

笔记

oi

算法

数据结构

竞赛

C++

题解

C#

题目：JOU1013 链表划分

给定一个单链表，要对其应用快速排序算法排序，需要选定一个Pivot(划分元素或枢纽元）对单链表进行划分，如果链表的长度是L，则选择第 ⌊L+12⌋⌊\frac{L+1}{2}⌋ 个节点的值作为Pivot。请编写程序将链表元素进行划分，使得所有小于Pivot的结点都排在Pivot所在结点的前面，而所有大于Pivot的结点都排在Pivot所在结点的后面。但每一部分内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，则输出应该为 -4→0→-6→-2→5→18→7→10→11。

输入格式：

每个输入包含一个测试用例。每个测试用例第 1 行给出：第 1 个结点的地址；结点总个数，即正整数 N(≤105)N(≤10^5)。结点的地址是 5 位非负整数，NULL 地址用 −1−1 表示。

接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址；Data 是该结点保存的数据，为[−105,105][−10^5, 10^5]区间内的整数；Next 是下一结点的地址。题目保证给出的链表不为空，题目保证所有结点保存的数据两两不同。

输出格式：

对每个测试用例，按链表从头到尾的顺序输出划分后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 9
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

输出样例：

33218 -4 00000
00000 0 68237
68237 -6 48652
48652 -2 99999
99999 5 00100
00100 18 12309
12309 7 23333
23333 10 27777
27777 11 -1

题解

读入并存储数据

题目通过 Address Data Next 描述链表结构，因此我们可以通过数组或哈希表模拟内存的方式来表达这个链表的结构，而不是真的去写一个链表，节省了很多心智负担。

又因为地址是 5 位非负整数，如果使用数组模拟的话这个数组开起来会比较大，输出时又要把地址进行类型转换并补0，所以不如干脆直接读入地址的字符串形式，并通过哈希表模拟内存来存储这个链表。

下面是相关逻辑的 C++ 实现：

先写上我的固定答题模板：

#include <bits/stdc++.h>
using namespace std;

using i64 = int64_t;
using i32 = int32_t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    return 0;
}

声明链表节点结构：

struct Node {
    string addr, next; // 地址以字符串形式存储
    i64 val; // 题目中是 data, 我习惯用 val
};

读入第一行数据：

// ...
int main() {
    // ...
    string head;
    i64 len;
    cin >> head >> len;
}

创建哈希表来模拟内存：

// ...
int main() {
    // ...
    map<string, Node> memo;
}

读入数据并存入哈希表：

// ...
int main() {
    // ...
    for (i64 i = 0; i < len; ++i) {
        string addr, next;
        i64 val;
        cin >> addr >> val >> next;
        memo[addr] = {addr, next, val}; // 地址字符串作为哈希表的键 值为 Node
    }
}

找到 Pivot 节点

Pivot 节点的定义很简单：

如果链表的长度是L，则选择第⌊L+12⌋⌊\frac{L+1}{2}⌋个节点的值作为Pivot

所以我们可以方便地计算出 Pivot 节点的索引：

i64 pivot_index = (len + 1) / 2;

因为题目给出了链表头节点的地址，我们便可以轻松地遍历链表，找出 Pivot 节点：

// ...
int main() {
    // ...
    i64 pivot_index = (len + 1) / 2;
    Node curr = memo[head], pivot_node;
    for (i64 i = 1; true; ++i) { // 这里 i 初始化为 1 更直观
        if (i == pivot_index) {
            pivot_node = curr;
            break;
        }
        curr = memo[curr.next];
    }
}

重排链表

得到 Pivot 节点后，便可以通过数据大小比较来重排链表，根据题目，我们可以将重排后的链表表示成下面三部分组成：

[值小于 Pivot 节点的节点们] -> (Pivot 节点) -> [值大于 Pivot 节点的节点们]

题目还要求，每部分的节点相对位置保持不变，因此我们便可以通过两个队列和一个 Node 对象 (其实已经有了，见上面的代码) 来暂时存储节点以保证每部分内的节点相对位置保持不变：

queue<Node> lesser, greater; // 当然 如果你乐意，vector 也可以胜任此工作

通过按正向顺序遍历链表并依次将每个节点的值和 Pivot 节点的值做比较，可以构建出这两个队列。

// ...
int main() {
    // ...
    curr = memo[head]; // 记得将 curr 重新定位到链表头
    queue<Node> lesser, greater;
    while (true) {
        if (curr.val < pivot_node.val) {
            lesser.push(curr);
        }
        // 注意这里不能直接else 否则会导致 Pivot 节点进入 greater 队列
        if (curr.val > pivot_node.val) {
            greater.push(curr);
        }
        
        // 在 NULL 地址时结束遍历
        if (curr.next == "-1") break;
        
        // 将 curr 定位到下一节点
        curr = memo[curr.next];
    }
}

输出链表

这一部分的工作很简单，按照上面的结构依次输出就行

// ...
int main() {
    // ...
    // 当然你也可以写 lesser.size()，不过我觉得这样写更符合直觉
    while (!lesser.empty()) {
        auto node = lesser.front(); // 取出队头的节点元素
        lesser.pop(); // 弹出队头
        
        cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    }
    
    // 输出 Pivot 节点
    cout << pivot_node.addr << ' ' << pivot_node.val << ' ' << pivot_node.next << '\n';
    
   	while (!greater.empty()) {
        auto node = greater.front();
        greater.pop();
        
        cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    }
}

测试

将上面的代码组合在一起，输入示例输入进行测试：

#include <bits/stdc++.h>
using namespace std;

using i64 = int64_t;
using i32 = int32_t;

struct Node {
    string addr, next; // 地址以字符串形式存储
    i64 val; // 题目中是 data, 我习惯用 val
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string head;
    i64 len;
    cin >> head >> len;

    map<string, Node> memo;
    for (i64 i = 0; i < len; ++i) {
        string addr, next;
        i64 val;
        cin >> addr >> val >> next;
        memo[addr] = {addr, next, val}; // 地址字符串作为哈希表的键 值为 Node
    }

    i64 pivot_index = (len + 1) / 2;
    Node curr = memo[head], pivot_node;
    for (i64 i = 1; true; ++i) { // 这里 i 初始化为 1 更直观
        if (i == pivot_index) {
            pivot_node = curr;
            break;
        }
        curr = memo[curr.next];
    }

    curr = memo[head]; // 记得将 curr 重新定位到链表头
    queue<Node> lesser, greater;
    while (true) {
        if (curr.val < pivot_node.val) {
            lesser.push(curr);
        }
        // 注意这里不能直接else 否则会导致 Pivot 节点进入 greater 队列
        if (curr.val > pivot_node.val) {
            greater.push(curr);
        }
        
        // 在 NULL 地址时结束遍历
        if (curr.next == "-1") break;
        
        // 将 curr 定位到下一节点
        curr = memo[curr.next];
    }

    // 当然你也可以写 lesser.size()，不过我觉得这样写更符合直觉
    while (!lesser.empty()) {
        auto node = lesser.front(); // 取出队头的节点元素
        lesser.pop(); // 弹出队头
        
        cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    }
    
    // 输出 Pivot 节点
    cout << pivot_node.addr << ' ' << pivot_node.val << ' ' << pivot_node.next << '\n';
    
   	while (!greater.empty()) {
        auto node = greater.front();
        greater.pop();
        
        cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    }

    return 0;
}

输出以下数据：

33218 -4 00000
00000 0 99999
68237 -6 23333
48652 -2 -1
99999 5 68237
00100 18 12309
12309 7 33218
23333 10 27777
27777 11 48652

与测试数据比较：

33218 -4 00000
00000 0 68237
68237 -6 48652
48652 -2 99999
99999 5 00100
00100 18 12309
12309 7 23333
23333 10 27777
27777 11 -1

嗯，不能说是完全一致吧，只能说是错了一堆（；´д｀）ゞ

重新构建链表

仔细观察我们得到的输出数据与示例数据的差异，不难发现，题目要求我们在排列后重新构建链表，即修改原有每一个节点的地址和下一节点的地址，使得输出数据也是一个合法的链表。

这里我们建立一个 ans 队列来帮助我们构建输出链表：

// ...
int main() {
    // ...
    queue<Node> ans;
    
    while (!lesser.empty()) {
        auto node = lesser.front(); // 取出队头的节点元素
        lesser.pop(); // 弹出队头
        
        // 当是第一个节点的时候
        if (ans.empty()) {
            // 直接推入队列
            ans.push(node);
            // 通过卫语句直接进入下一次循环 不用写 else 了
            continue;
        }
        
        // 否则先修改前一个节点的 next 属性为本节点的地址
        ans.back().next = node.addr;
        // 将节点推入队列尾
        ans.push(node);
    }
    
    // 同样的逻辑用于 Pivot 节点和 greater 队列
    ans.back().next = pivot_node.addr;
    ans.push(pivot_node);
    
    while (!greater.empty()) {
        auto node = greater.front();
        greater.pop();
        
        ans.back().next = node.addr;
        ans.push(node);
    }
    
    // 别忘了修改最后一个节点的 next 属性为 -1
    
}

接下来就可以进行输出了：

// ...
int main() {
    // ...
    while (!ans.empty()) {
        auto node = ans.front();
        ans.pop();

        cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    }
}

组合代码，重新测试：

#include <bits/stdc++.h>
using namespace std;

using i64 = int64_t;
using i32 = int32_t;

struct Node {
    string addr, next; // 地址以字符串形式存储
    i64 val; // 题目中是 data, 我习惯用 val
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string head;
    i64 len;
    cin >> head >> len;

    map<string, Node> memo;
    for (i64 i = 0; i < len; ++i) {
        string addr, next;
        i64 val;
        cin >> addr >> val >> next;
        memo[addr] = {addr, next, val}; // 地址字符串作为哈希表的键 值为 Node
    }

    i64 pivot_index = (len + 1) / 2;
    Node curr = memo[head], pivot_node;
    for (i64 i = 1; true; ++i) { // 这里 i 初始化为 1 更直观
        if (i == pivot_index) {
            pivot_node = curr;
            break;
        }
        curr = memo[curr.next];
    }

    curr = memo[head]; // 记得将 curr 重新定位到链表头
    queue<Node> lesser, greater;
    while (true) {
        if (curr.val < pivot_node.val) {
            lesser.push(curr);
        }
        // 注意这里不能直接else 否则会导致 Pivot 节点进入 greater 队列
        if (curr.val > pivot_node.val) {
            greater.push(curr);
        }
        
        // 在 NULL 地址时结束遍历
        if (curr.next == "-1") break;
        
        // 将 curr 定位到下一节点
        curr = memo[curr.next];
    }

    queue<Node> ans;
    
    while (!lesser.empty()) {
        auto node = lesser.front(); // 取出队头的节点元素
        lesser.pop(); // 弹出队头
        
        // 当是第一个节点的时候
        if (ans.empty()) {
            // 直接推入队列
            ans.push(node);
            // 通过卫语句直接进入下一次循环 不用写 else 了
            continue;
        }
        
        // 否则先修改前一个节点的 next 属性为本节点的地址
        ans.back().next = node.addr;
        // 将节点推入队列尾
        ans.push(node);
    }
    
    // 同样的逻辑用于 Pivot 节点和 greater 队列
    ans.back().next = pivot_node.addr;
    ans.push(pivot_node);
    
    while (!greater.empty()) {
        auto node = greater.front();
        greater.pop();
        
        ans.back().next = node.addr;
        ans.push(node);
    }

    // 别忘了修改最后一个节点的 next 属性为 -1
    ans.back().next = "-1";

    while (!ans.empty()) {
        auto node = ans.front();
        ans.pop();
        
        cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    }

    return 0;
}

输入数据，得到输出结果：

33218 -4 00000
00000 0 68237
68237 -6 48652
48652 -2 99999
99999 5 00100
00100 18 12309
12309 7 23333
23333 10 27777
27777 11 -1

核对数据，和样例结果一致，提交代码！

image-20240323025631610

但是很遗憾，这一版代码只能通过不到一半的测试点 ┗|｀O′|┛

借由 Runtime Error 找到错误点

说实话，当程序爆出 Runtime Error 的时候应该是要感到高兴的，因为找到程序运行时的逻辑错误远比找到不符合题目的逻辑错误要更简单，通过不断由底向上注释逻辑段的方法我们可以快速定位到哪里出现了 Runtime Error：

// ...
int main() {
    // ...
    queue<Node> ans;
    
    while (!lesser.empty()) {
        auto node = lesser.front(); // 取出队头的节点元素
        lesser.pop(); // 弹出队头
        
        // 当是第一个节点的时候
        if (ans.empty()) {
            // 直接推入队列
            ans.push(node);
            // 通过卫语句直接进入下一次循环 不用写 else 了
            continue;
        }
        
        // 否则先修改前一个节点的 next 属性为本节点的地址
        ans.back().next = node.addr;
        // 将节点推入队列尾
        ans.push(node);
    }
    
    // 同样的逻辑用于 Pivot 节点和 greater 队列
    ans.back().next = pivot_node.addr;
    ans.push(pivot_node);
    
    // while (!greater.empty()) {
    //     auto node = greater.front();
    //     greater.pop();
        
    //     ans.back().next = node.addr;
    //     ans.push(node);
    // }

    // // 别忘了修改最后一个节点的 next 属性为 -1
    // ans.back().next = "-1";

    // while (!ans.empty()) {
    //     auto node = ans.front();
    //     ans.pop();
        
    //     cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    // }

    return 0;
}

当注释了将 Pivot 节点加入 ans 队列之后的逻辑后，提交后的结果如下：

image-20240323120525840

可以看到对应测试点的 RE 依旧存在

而当我们把将 Pivot 节点加入 ans 队列的逻辑也注释掉后：

// ...
int main() {
    // ...
    queue<Node> ans;
    
    while (!lesser.empty()) {
        auto node = lesser.front(); // 取出队头的节点元素
        lesser.pop(); // 弹出队头
        
        // 当是第一个节点的时候
        if (ans.empty()) {
            // 直接推入队列
            ans.push(node);
            // 通过卫语句直接进入下一次循环 不用写 else 了
            continue;
        }
        
        // 否则先修改前一个节点的 next 属性为本节点的地址
        ans.back().next = node.addr;
        // 将节点推入队列尾
        ans.push(node);
    }
    
    // 同样的逻辑用于 Pivot 节点和 greater 队列
    // ans.back().next = pivot_node.addr;
    // ans.push(pivot_node);
    
    // while (!greater.empty()) {
    //     auto node = greater.front();
    //     greater.pop();
        
    //     ans.back().next = node.addr;
    //     ans.push(node);
    // }

    // // 别忘了修改最后一个节点的 next 属性为 -1
    // ans.back().next = "-1";

    // while (!ans.empty()) {
    //     auto node = ans.front();
    //     ans.pop();
        
    //     cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    // }

    return 0;
}

image-20240323120807775

可以看到 RE 全部消失了，说明 RE 出现在将 Pivot 节点加入 ans 队列的逻辑中

幸运的是，我们定位到的错误点只有两行代码，而可能出现 RE 的代码只有一行：

ans.back().next = pivot_node.addr;

而这行代码出现 RE 的情况也不难想到，即 ans 队列为空

我们可以在这行代码前使用断言（assert）验证我们的猜想：

assert(!ans.empty());

提交代码进行测试：

image-20240323121554339

可以看到原来的段错误变成了 Aborted，说明我们的猜想正确，现在我们可以带着这一情况回到题面分析可能出现这种情况的原因了！

再审题目 分析 RE 错误原因

通过重审题目 不难发现题目中并没有说明链表中一定同时包含节点值小于 Pivot 节点的值和 大于 Pivot 节点的值的部分，甚至在链表长度为 1 的时候，只存在 Pivot 节点。而如果不存在小于 Pivot 节点的值的部分时，ans 队列中没有任何节点，自然也就产生了 RE！

因此我们可以在以上分析的基础上修改相关代码：

// ...
int main() {
    // ...
    // 同样的逻辑用于 Pivot 节点和 greater 队列
    // 若存在小于 Pivot 节点的部分 则先修改上一结点的 next 属性
    if (!ans.empty()) {
        ans.back().next = pivot_node.addr;
    }
    ans.push(pivot_node);
    // ...
}

代码全貌如下：

#include <bits/stdc++.h>
using namespace std;

using i64 = int64_t;
using i32 = int32_t;

struct Node {
    string addr, next; // 地址以字符串形式存储
    i64 val; // 题目中是 data, 我习惯用 val
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string head;
    i64 len;
    cin >> head >> len;

    map<string, Node> memo;
    for (i64 i = 0; i < len; ++i) {
        string addr, next;
        i64 val;
        cin >> addr >> val >> next;
        memo[addr] = {addr, next, val}; // 地址字符串作为哈希表的键 值为 Node
    }

    i64 pivot_index = (len + 1) / 2;
    Node curr = memo[head], pivot_node;
    for (i64 i = 1; true; ++i) { // 这里 i 初始化为 1 更直观
        if (i == pivot_index) {
            pivot_node = curr;
            break;
        }
        curr = memo[curr.next];
    }

    curr = memo[head]; // 记得将 curr 重新定位到链表头
    queue<Node> lesser, greater;
    while (true) {
        if (curr.val < pivot_node.val) {
            lesser.push(curr);
        }
        // 注意这里不能直接else 否则会导致 Pivot 节点进入 greater 队列
        if (curr.val > pivot_node.val) {
            greater.push(curr);
        }
        
        // 在 NULL 地址时结束遍历
        if (curr.next == "-1") break;
        
        // 将 curr 定位到下一节点
        curr = memo[curr.next];
    }

    queue<Node> ans;
    
    while (!lesser.empty()) {
        auto node = lesser.front(); // 取出队头的节点元素
        lesser.pop(); // 弹出队头
        
        // 当是第一个节点的时候
        if (ans.empty()) {
            // 直接推入队列
            ans.push(node);
            // 通过卫语句直接进入下一次循环 不用写 else 了
            continue;
        }
        
        // 否则先修改前一个节点的 next 属性为本节点的地址
        ans.back().next = node.addr;
        // 将节点推入队列尾
        ans.push(node);
    }
    
    // 同样的逻辑用于 Pivot 节点和 greater 队列
    // 若存在小于 Pivot 节点的部分 则先修改上一结点的 next 属性
    if (!ans.empty()) {
        ans.back().next = pivot_node.addr;
    }
    ans.push(pivot_node);
    
    while (!greater.empty()) {
        auto node = greater.front();
        greater.pop();
        
        ans.back().next = node.addr;
        ans.push(node);
    }

    // 别忘了修改最后一个节点的 next 属性为 -1
    ans.back().next = "-1";

    while (!ans.empty()) {
        auto node = ans.front();
        ans.pop();
        
        cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    }

    return 0;
}

image-20240323125107293

可以看到，我们已经消除了所有 RE，但仍然存在部分错误

留意特殊错误的信息

可以看到，有一类特殊的错误信息是我们输出的内容和标准答案的长度不同，这不免让我产生了疑问，难道我输出的内容长度与输入内容不一致？这完全是可能的，是否因为我们中间处理逻辑的错误导致部分节点并没有被处理到呢？

我们可以写一个断言来判断是否存在这种情况：

// ...
int main() {
    //...
	
    assert(ans.size() == memo.size());
    
    while (!ans.empty()) {
        auto node = ans.front();
        ans.pop();
        
        cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    }

    // ...
}

提交代码查看结果：

image-20240323125946393

好家伙，居然有这么多测试点出现了输出的链表长度和输入不一致的情况！但是排查了许久，我也没发现我们在对节点进行分类并重新排列的代码中可能出现遗漏节点的情况。不怕丢人地说，我在这一点上思考了近一个小时也没想通问题出在哪里。

难道就这样放弃吗？

回归题面 重新思考

通过反复审题，我们其实可以发现一个问题：题目并没有保证给出的所有节点都在一个链表内

也就是说，可能存在测试数据给出的节点不属于待分割链表的情况！

因此，我们可以将题目给出的节点先读入 draft_memo 这个哈希表中，然后从链表头开始遍历，并把遍历的节点加入 memo 这个哈希表中，以此来过滤掉那些不属于这个链表的节点

相关代码的实现如下：

// ...
int main() {
    // ...
    map<string, Node> draft_memo, memo;
    for (i64 i = 0; i < len; ++i) {
        string addr, next;
        i64 val;
        cin >> addr >> val >> next;
        draft_memo[addr] = {addr, next, val}; // 地址字符串作为哈希表的键 值为 Node
    }

    // 过滤掉草稿 memo 中不在链表中的节点
    Node curr = draft_memo[head];
    while (true) {
        memo[curr.addr] = curr;
        if (curr.next == "-1") break;
        curr = draft_memo[curr.next];
    }
    
    // ...
}

修改代码后提交：

image-20240323130820019

??? 不对啊为什么还没过呢

再次查看自己的代码实现，可以发现，链表的长度不再是读入的 len，而是 memo 的长度

因此也别忘了修改求 Pivot 节点的实现：

i64 pivot_index = (memo.size() + 1) / 2;

整合上述所有实现的代码如下：

#include <bits/stdc++.h>
using namespace std;

using i64 = int64_t;
using i32 = int32_t;

struct Node {
    string addr, next; // 地址以字符串形式存储
    i64 val; // 题目中是 data, 我习惯用 val
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string head;
    i64 len;
    cin >> head >> len;

    map<string, Node> draft_memo, memo;
    for (i64 i = 0; i < len; ++i) {
        string addr, next;
        i64 val;
        cin >> addr >> val >> next;
        draft_memo[addr] = {addr, next, val}; // 地址字符串作为哈希表的键 值为 Node
    }

    // 过滤掉草稿 memo 中不在链表中的节点
    Node curr = draft_memo[head];
    while (true) {
        memo[curr.addr] = curr;
        if (curr.next == "-1") break;
        curr = draft_memo[curr.next];
    }

    i64 pivot_index = (memo.size() + 1) / 2;
    Node pivot_node;
    curr = memo[head];
    for (i64 i = 1; true; ++i) { // 这里 i 初始化为 1 更直观
        if (i == pivot_index) {
            pivot_node = curr;
            break;
        }
        curr = memo[curr.next];
    }

    curr = memo[head]; // 记得将 curr 重新定位到链表头
    queue<Node> lesser, greater;
    while (true) {
        if (curr.val < pivot_node.val) {
            lesser.push(curr);
        }
        // 注意这里不能直接else 否则会导致 Pivot 节点进入 greater 队列
        if (curr.val > pivot_node.val) {
            greater.push(curr);
        }
        
        // 在 NULL 地址时结束遍历
        if (curr.next == "-1") break;
        
        // 将 curr 定位到下一节点
        curr = memo[curr.next];
    }

    queue<Node> ans;
    
    while (!lesser.empty()) {
        auto node = lesser.front(); // 取出队头的节点元素
        lesser.pop(); // 弹出队头
        
        // 当是第一个节点的时候
        if (ans.empty()) {
            // 直接推入队列
            ans.push(node);
            // 通过卫语句直接进入下一次循环 不用写 else 了
            continue;
        }
        
        // 否则先修改前一个节点的 next 属性为本节点的地址
        ans.back().next = node.addr;
        // 将节点推入队列尾
        ans.push(node);
    }
    
    // 同样的逻辑用于 Pivot 节点和 greater 队列
    // 若存在小于 Pivot 节点的部分 则先修改上一结点的 next 属性
    if (!ans.empty()) {
        ans.back().next = pivot_node.addr;
    }
    ans.push(pivot_node);
    
    while (!greater.empty()) {
        auto node = greater.front();
        greater.pop();
        
        ans.back().next = node.addr;
        ans.push(node);
    }

    // 别忘了修改最后一个节点的 next 属性为 -1
    ans.back().next = "-1";

    while (!ans.empty()) {
        auto node = ans.front();
        ans.pop();
        
        cout << node.addr << ' ' << node.val << ' ' << node.next << '\n';
    }

    return 0;
}

提交我们的代码：

image-20240323131046719

恭喜 AC ！

后记

我的实现思路既不是最简洁的，效率也不是最高的。但我希望这种麻烦的逐步思考的思路能帮到大家，特别是希望帮到缺乏基础的同学理解通过这道题目并学到一些调试程序定位错误位置的方法和思路。这是本人第一次写题解，如果有问题能够被指正我会虚心接收，如果你由我的实现启发而改进出了更好的实现也欢迎和我讨论交流，谢谢阅读！

补题笔记：JOU1013 链表划分

作者

WhitePaper 白芷

发布日期

2024 - 03 - 23

许可证 CC BY-NC-SA 4.0
Avatar
WhitePaper 白芷

Ad Astra Per Aspera.

分类

浏览器扩展

1

Minecraft

1

影视

1

编程

1

算法笔记

2

数据结构

1

设计模式

1
标签

B站

Bilibili

Minecraft

Fabric

字幕

编程

设计模式

Golang

笔记

oi

算法

数据结构

竞赛

C++

题解

C#