/**
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
**/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode little = new ListNode();
ListNode littleNext = new ListNode();
ListNode big = new ListNode();
ListNode bigNext = new ListNode();
little.next = littleNext;
big.next = bigNext;
while(head != null){
ListNode next = new ListNode(head.val,null);
if(head.val < x){
littleNext.next = next;
littleNext = littleNext.next;
}else{
bigNext.next = next;
bigNext = bigNext.next;
}
head = head.next;
}
littleNext.next = big.next.next;
return little.next.next;
}
}
