题目描述：
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:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
中文描述：
给定一个链表和一个数字，把链表中小于这个数字的节点调整到节点前面，返回这个新的链表。
解题思路：
两次遍历链表，第一次遍历时将小于x的节点值，则将这个节点连接到结果链表中，第二次遍历链表，如果节点值大于等于x则将结果连接到结果链表中。
代码（java）：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if(head==null || head.next==null)return head;
ListNode small=new ListNode(0),p=head;
ListNode cur=small;
while(p!=null){
if(p.val<x){
cur.next=new ListNode(p.val);
cur=cur.next;
}
p=p.next;
}
p=head;
while(p!=null){
if(p.val>=x){
cur.next=new ListNode(p.val);
cur=cur.next;
}
p=p.next;
}
return small.next;
}
}
