划分链表

题号：NC163
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出一个长度为 n 的单链表和一个值 x ，单链表的每一个值为 list_i ，请返回一个链表的头结点，要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧，并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。

例如：

给出 $1 \to 4 \to 3 \to 2 \to 5 \to 2$ 和 $x = 3$

返回 $1 \to 2 \to 2 \to 4 \to 3 \to 5$

数据范围： $n \le 200$ ， $-100 \le list[i] \le 100$

进阶：时间复杂度 $O(n)$ ，空间复杂度 $O(1)$

示例1

复制

{1,4,3,2,5,2},3

复制

{1,2,2,4,3,5}

示例2

复制

{1,2,3,4,1},5

复制

{1,2,3,4,1}