因为要求稳定，所以交换是不可以的。这里可以由O(1)的方法 不需要新建结点。
/以pos为遍历浮标，pre1，pre2分开引用不同条件的数，不会存在链表原有数缺失的情况。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(0) ;
ListNode dummy2= new ListNode(0);
ListNode pre1 = dummy1;
ListNode pre2= dummy2;
ListNode pos = head ;
//以pos为遍历浮标，pre1，pre2分开引用不同条件的数，不会存在链表原有数缺失的情况。
while(pos!=null)
{
if(pos.val<x)
{
pre1.next=pos;
pre1=pre1.next;
}
else
{
pre2.next=pos;
pre2=pre2.next;
}
pos=pos.next;
}
// 需要在最后对pre2的末尾进行清零 不然会形成环,
pre2.next=null;
pre1.next=dummy2.next;
return dummy1.next;
}
}
