将单向链表按某值划分成左边小、中间相等、右边大的形式
给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整 链表 的函数，将链表调整为左部分都是小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。除这个要求外，对调整后的节点顺序没有更多的要求。
例如：链表9->0->4->5->1,pivot=3.
调整后链表可以是1->0->4->9->5,也可以是0->1->9->5->4.总之，满足左部分都是小于3的节点。中间部分都是等于3的节点（本例中中间部分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。
进阶：在原问题的要求上再增加如下两个要求。
在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左到右的顺序与原链表中节点的先后次序一致。
例如：9->0->4->5->1，pivot=3.调整后的链表是0->1->9->4->5.在满足原问题要求的同时，左部分节点从左到右为0、1.在原链表中也是先出现0，后出现1；中间部分在本例中为空，不再讨论；右部分节点从左到右为9、4、5.在远链表中也是先出现9，然后出现4，最后出现5.
2.如果链表长度为N， 时间复杂度 请达到O（N）。额外空间复杂度达到O（1）。
难度：两颗星
解析：普通解法的时间复杂度为O（N）。额外空间复杂度为O（N），就是把链表中的所有节点放入一个额外的数组中，然后统一调整位置的办法。具体过程如下：
先遍历一遍链表，为了得到链表的长度，假设长度为N。
生成长度为N的Node类型的数组nodeArr，然后遍历一次链表，将节点依次放进nodeArr中。在这里先不用LinkList或ArrayList等java提供的结构，因为一个纯粹的数组结果比较利于步骤3的调整。
在nodeArr中把小于pivot的节点放在左边，把相等的放中间，把大于的放在右边。也就是改进了 快速排序 中 partition 的调整过程，即如下代码中的arrPartition方法。
经过步骤3的调整后，nodeArr是满足题目要求的节点顺序，只要把nodeArr中的节点依次重连起来即可，整个过程结束。
全部过程请看如下代码中的listPartition1方法：
下面来看增加要求后的进阶解法。对每部分都增加了节点顺序要求，同时时间复杂度仍为O（N），额外空间复杂度为O（1）。既然额外空间复杂度为O（1），说明实现时只能使用有限的几个变量来完成所有的调整。
进阶解法的具体过程如下：
将原链表中的所有节点依次划分进三个链表，三个链表分别为small代表左部分，equal代表中间部分，big代表右部分。
例如，链表7->9->1->8->5->2->5,pivot=5.在划分之后，small，equal，big分别为：
small：1->2->null
equal:5->->5->null
big:7->9->8->null
2.将samall、equal、和big三个链表重新串起来即可
3.整个过程需要特别注意对null节点的判断和处理。
进阶解法还是主要考查面试者利用有限几个变量调整链表的代码实现能力，全部进阶解法请参看如下代码中的listPartition2方法：
将单向链表按某值分成左边小、中间相等、右边大的形式的问题就讲到这，希望能给大家有一点收益。
