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.
For example, Given1->4->3->2->5->2and x = 3, return1->2->2->4->3->5.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode partition(ListNode head, int x) { if(head == null) return null; ListNode fake1 = new ListNode(0); ListNode fake2 = new ListNode(0); fake1.next = head; ListNode p = head; ListNode pre = fake1; ListNode p2 = fake2; while(p != null) { if(p.val < x) { p = p.next; pre = pre.next; }else { p2.next = p; pre.next = p.next; p = p.next; p2 = p2.next; } } p2.next = null; pre.next = fake2.next; return fake1.next; } }