1+ /*
2+ Author: King, higuige@gmail.com
3+ Date: Oct 7, 2014
4+ Problem: Partition List
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/partition-list/
7+ Notes:
8+ 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.
9+ You should preserve the original relative order of the nodes in each of the two partitions.
10+ For example,
11+ Given 1->4->3->2->5->2 and x = 3,
12+ return 1->2->2->4->3->5.
13+
14+ Solution: ...
15+ */
16+
17+ /**
18+ * Definition for singly-linked list.
19+ * public class ListNode {
20+ * int val;
21+ * ListNode next;
22+ * ListNode(int x) {
23+ * val = x;
24+ * next = null;
25+ * }
26+ * }
27+ */
28+ public class Solution {
29+ public ListNode partition_1 (ListNode head ,int x ) {
30+ ListNode leftdummy =new ListNode (-1 );
31+ ListNode rightdummy =new ListNode (-1 );
32+ ListNode lhead =leftdummy ;
33+ ListNode rhead =rightdummy ;
34+
35+ for (ListNode cur =head ;cur !=null ;cur =cur .next ){
36+ if (cur .val <x ){
37+ lhead .next =cur ;
38+ lhead =lhead .next ;
39+ }else {
40+ rhead .next =cur ;
41+ rhead =rhead .next ;
42+ }
43+ }
44+ lhead .next =rightdummy .next ;
45+ rhead .next =null ;
46+ return leftdummy .next ;
47+ }
48+ public ListNode partition (ListNode head ,int x ) {
49+ ListNode dummy =new ListNode (-1 );
50+ dummy .next =head ;
51+ ListNode cur =dummy ;
52+ ListNode ins =dummy ;
53+ while (cur .next !=null &&cur .next .val <x ) {
54+ cur =cur .next ;
55+ ins =ins .next ;
56+ }
57+ while (cur .next !=null ) {
58+ if (cur .next .val >=x ) {
59+ cur =cur .next ;
60+ }else {
61+ ListNode node =cur .next ;
62+ cur .next =cur .next .next ;
63+ node .next =ins .next ;
64+ ins .next =node ;
65+ ins =ins .next ;
66+ }
67+ }
68+ return dummy .next ;
69+ }
70+ }
