1075 链表元素分类 (25 分)

题目

题目链接

题解

链表。

整体思路比较好想：

1. 先创建两个新链表（负数链表和正数链表），按照原串的顺序依次遍历每个节点，将负数节点插入到负数链表中，正数节点插入到正数链表中。
2. 再创建两个新链表（小于k链表和大于k链表），按照正数链表的顺序依次遍历每个节点，将小于k的节点插入到小于k链表中，大于k的节点插入到大于k链表中。
3. 将三个串头尾相连，最后输出（如果不拼接直接输出的话需要处理很多边界情况，不方便，不如先拼接起来，也就是前一个链表结尾的节点的next指向下一个链表开头的位置）

还有一些细节需要处理：

1. 获取了三段链表（负数链表、小于k链表和大于k链表）的首节点和尾节点后将三者顺次链接的时候要考虑到如果负数链表是空，该如何处理？如果小于k链表是空，该如何处理？
2. 拼接完成后，需要顺序遍历新的整个链表，那么新的链表头该如何确定？就一定是负数链表的首节点吗？如果负数链表为空呢？如果小于k链表为空呢？

具体细节的实现看代码吧！

代码

#include
using namespace std;
const int N = 5e6+10;

struct Node {
	int val, ne;
} node[N];

int main()
{
	int st, n, k;
	cin >> st >> n >> k;
	for (int i = 0;i > add >> val >> ne;
		node[add].val = val;
		node[add].ne = ne;
	}	
	
	int neg_st = -1, pos_st = -1;
	int p = st, neg = -1, pos = -1;
	while (p != -1) {
		if (node[p].val