# 题目

Given a singly linked list, you are supposed to rearrange its elements so that all the negative values appear before all of the non-negatives, and all the values in [0, K] appear before all those greater than K. The order of the elements inside each class must not be changed. For example, given the list being 18→7→-4→0→5→-6→10→11→-2 and K being 10, you must output -4→-6→-2→7→0→5→10→18→11.

### Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive $N (≤10^5)$ which is the total number of nodes, and a positive $K (≤10^3)$. The address of a node is a 5-digit nonnegative integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

where Address is the position of the node, Data is an integer in $[−10^5,10^5]$, and Next is the position of the next node. It is guaranteed that the list is not empty.

### Output Specification:

For each case, output in order (from beginning to the end of the list) the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

# 题解

## 思路

• 题目的意思是
• 给了你一串链表
• 然后让你把链表划分为三部分
• 小于0的
• 0到K之间的
• 大于K的
• 依次连接起来，其中每一部分保持原来的顺序不变
• 我们设三个列表分表保存这三部分，输出的时候合并在一块，即可。

## 数据结构

• K 即题目里的K
• 三个部分的列表依次命名为
• negative
• zero_to_K
• more_than_K
• （很直观的命名吧！
• _next 数组存放所有地址的下一个地址（原链表中的）
• 下标是原地址
• 值是它的下一个地址
• val 数组存放所有地址的值
• 下标是地址
• 值是值（绕口令？
• node 是遍历用节点
• ans 将前面三个部分连接起来

## 算法

• 首先读入数据，添加到_next和val数组当中。
• 从起始节点开始遍历，并按情况添加到三个部分的列表。这样可以保证三个部分的正好也是按原来的顺序的。
• 将三个部分拼接在一起。
• 输出即可。

## 代码

• 这道题使用Python会有一个点超时，建议使用C++