题目：

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

假设有一链表：

给定x=6

MySingleList mySingleList  = new MySingleList();mySingleList.addFirst(7);mySingleList.addFirst(3);mySingleList.addFirst(9);mySingleList.addFirst(6);mySingleList.addFirst(5);mySingleList.show();

题解：

显然x将链表分成了两段 ，又因为不能改变原来的数据顺序，显然可以借用头插法或尾插法，

思路：设置q1为小于x的链表，h1为大于x的链表

1.遍历链表，当链表head.val >x时尾插q1,否则尾插h1

2.连接q1,h1

1.为了记录起始位置设置q1,q2,h1,h2,以方便后期连接。

ListNode q1 = null;
ListNode q2 = null;
ListNode h1 = null;
ListNode h2 = null;
ListNode cur = head;

考虑到第一次插入时q1=null,无法调用q1.next因此if判断

   if(q2 == null) {q2 = cur;q1 = cur;}else {q2.next = cur;q2 = q2.next;}
cur = cur.next;

同理：

                if(h2 == null) {h2 = cur;h1 = cur;}else {h2.next = cur;h2 = h2.next;}cur = cur.next; 

2.连接时要注意q1,q2是否可以调用next

        if(q2 != null) {q2.next = h1;}else {q1 = h1;}

最后要注意的是将h2.next置为null

        if(h2 != null) {h2.next = null;}return q1;