Description

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.

Example

Given 1->4->3->2->5->2->null and x = 3,

return 1->2->2->4->3->5->null.

看到“partition”，还以为是快速排序呢。。。题目的意思是，给一个链表，再给一个数。将链表中的数分为两个类：小于x、大于等于x。返回值为该类型的ListNode，将小于x的放前面，大于等于x的，放在后面。先贴给图：

哈哈哈，其实思路也挺简单的，不知道怎么就成最快的了。

思路：按照我分析的，将原链表拆分成两个链表，最后再合并起来。代码如下：

/** * Definition for ListNode * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    /**     * @param head: The first node of linked list     * @param x: An integer     * @return: A ListNode     */    public ListNode partition(ListNode head, int x) {        // write your code here        //放值小于x的结点，lp为插入low链表时的尾指针        ListNode low=null;        ListNode lp=low;        //放值大于等于x的结点，hp为插入high链表时的尾指针        ListNode high=null;        ListNode hp=high;        //p为循环的游标        ListNode p=head;        while(p!=null){            if(p.val