import java.util.Queue;

import java.util.concurrent.LinkedBlockingQueue;

/**

* 86. 分隔链表

*/

public class Partition {

public ListNode partition(ListNode head, int x) {

ListNode dummy = new ListNode(-1);

ListNode cur = dummy;

ListNode pos = head;

Queue<ListNode> queue = new LinkedBlockingQueue<>();

while (pos!=null){

if(pos.val<x){

cur.next = pos;

cur = cur.next;

}else{

queue.add(pos);

}

pos = pos.next;

}

while (!queue.isEmpty()){

cur.next = queue.poll();

cur = cur.next;

}

// 截断末尾

cur.next = null;

return dummy.next;

}

}