题解 | #划分链表#

思路：定义两个队列，一个队列用于存放小于x的数，一个队列用于存放大于等于x的数。得到这两个队列后，再依次取出里面的节点即可。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    public ListNode partition (ListNode head, int x) {
        // write code here
        
        if (null == head || null == head.next) {
            return head;
        }
        
        Queue<ListNode> queue1 = new LinkedList<>();
        Queue<ListNode> queue2 = new LinkedList<>();
        
        ListNode node = head;
        
        while (null != node) {
            if (node.val < x) {
                queue1.add(node);
            }
            else {
                queue2.add(node);
            }
            node = node.next;
        }
        
        if (!queue1.isEmpty()) {
            head = queue1.poll();
        }
        else {
            head = queue2.poll();
        }
        node = head;
        while (!queue1.isEmpty()) {
            node.next = queue1.poll();
            node = node.next;
        }
        while (!queue2.isEmpty()) {
            node.next = queue2.poll();
            node = node.next;
        }
        node.next = null;
        return head;
    }
}