一． 问题描述
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
二． 解题思路
本题思路：采用双指针的方法进行求解，并且需要了解如何链表如何交换节点。
步骤一：first指针指向小于目标值x的节点，而second指针指向first的下一个节点。
步骤二：从second指针指向的节点开始遍历，找到下一个小于目标值x的节点。
步骤三：将找到小于目标值x的节点插入到first指针的后一个节点中（百度如何交换链表节点）。将first指向first.next节点，返回步骤二。
（在这里第三步有一个简单方法，接着将将first指向first.next节点，second指向second.next节点，继续返回步骤三，会比较简单点。）
三． 执行结果
执行用时 :1 ms, 在所有 java 提交中击败了88.29%的用户
内存消耗 :35.6 MB, 在所有 java 提交中击败了57.14%的用户
四． Java代码
class Solution { public ListNode partition(ListNode head, int x) { if(head==null) { return head; } ListNode first=new ListNode(0); first.next=head; ListNode second=first; ListNode result=first; while(second.next!=null&&first.next!=null) { if(first.next.val<x) { first=first.next; }else { second=first.next; while(second.next!=null&&second.next.val>=x) { second=second.next; } ListNode temp=second.next; if(temp==null) { return result.next; } second.next=temp.next; temp.next=first.next; first.next=temp; first=first.next; } } return result.next; } }