/** * Source : https://oj.leetcode.com/problems/partition-list/ * * * Given a linked list and a value x, partition it such that all nodes less than x come * before nodes greater than or equal to x. * * You should preserve the original relative order of the nodes in each of the two partitions. * * For example, * Given 1->4->3->2->5->2 and x = 3, * return 1->2->2->4->3->5. */public class Partition {    /**     * 将链表中所有小于x的节点排在前面，然后是大于等于x的节点，partition后的链表要按照之前元素的相对顺序排序     *     * 将所有大于等于x的节点移除到另外一个链表，剩下的就是小于x的元素，然后将两个链表连接起来     *     * 因为链表头也可能被移除（可能变化），所以这里使用一个dummy节点指向原来的头，作为新的头，也就是链表的头     *     * @param head     * @return     */    public Node partition (Node head, int x) {        Node dummy = new Node();        dummy.next = head;        head = dummy;        Node greaterList = new Node();        Node greaterPointer = greaterList;        while (head != null && head.next != null) {            if (head.next.value >= x) {                // 加入新链表                greaterPointer.next = head.next;                head.next = head.next.next;                greaterPointer = greaterPointer.next;                greaterPointer.next = null;                // 从原来的链表移除            } else {                head = head.next;            }        }        head.next = greaterList.next;        return dummy.next;    }    private static class Node  implements Comparable
    
     {        int value;        Node next;        @Override        public String toString() {            return "Node{" +                    "value=" + value +                    ", next=" + (next == null ? "" : next.value) +                    '}';        }        @Override        public int compareTo(Node o) {            return this.value - o.value;        }    }    private static void print (Node node) {        while (node != null) {            System.out.println(node);            node = node.next;        }        System.out.println();    }    public Node createList (int[] arr) {        if (arr.length == 0) {            return null;        }        Node head = new Node();        head.value = arr[0];        Node pointer = head;        for (int i = 1; i < arr.length; i++) {            Node node = new Node();            node.value = arr[i];            pointer.next = node;            pointer = pointer.next;        }        return head;    }    public static void main(String[] args) {        Partition partition = new Partition();        int[] arr = new int[]{1,4,3,2,5,2};        int[] arr1 = new int[]{4,3,2,5,2};        print(partition.partition(partition.createList(arr1), 3));        print(partition.partition(partition.createList(arr), 3));    }}