描述
给出一个长度 n单链表和一个值 x，单链表的每个值为 listi ，请返回链表的头结点，要求新链表小于 x的节点全部在大于等于 x节点左侧，两部分内的节点与原链表保持相对顺序不变。
例如：
给出 1→4→3→2→5→2 1 \to 4 \to 3 \to 2 \to 5 \to 2 1→4→3→2→5→2 和 x=3 x = 3 x=3
返回 1→2→2→4→3→5 1 \to 2 \to 2 \to 4 \to 3 \to 5 1→2→2→4→3→5
数据范围：n≤200n \le 200 n≤200，?100≤list[i]≤100-100 \le list[i] \le 100 ?100≤list[i]≤100
高级：时间复杂 O(n)O(n)O(n) ， 空间复杂度 O(1)O(1)O(1)
示例1
输入：
{1，4，3，2，5，2}
返回值：
{、2、4、3
示例2
输入：
{1，2，3，4，1}
返回值：
(1)
public class Solution { public ListNode partition(ListNode head, int x) { if(head==null) return null; ListNode dummy1=new ListNode(0); ListNode dummy2=new ListNode(0); ListNode curr1=dummy1; ListNode curr2=dummy2; while(head!=null){ if(head.val<x){ curr1.next=head; curr1=curr1.next; }else{ curr2.next=head; curr2=curr2.next; } head=head.next; } curr2.next=null;//这句话很重要！如果链表的最后一个元素小于x，那么curr2.next 不为null curr1.next=dummy2.next; return dummy1.next; } }