//  Copyright 2016 The Sawdust Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
/*
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,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
 */

public class Leetcode86PartitionList {
    public class Solution {
        // beats 5.06% of java submissions on Feb 10, 2016
        private void process(ListNode node, int x, ListNode[] ts) {
            if (node != null) {
                if (node.val < x) {
                    ts[0].next = node;
                    ts[0] =ts[0].next;
                } else {
                    ts[1].next = node;
                    ts[1] = ts[1].next;
                }
               process(node.next, x, ts);
            }
        }

        public ListNode partition(ListNode head, int x) {
            ListNode smalsDumyHead = new ListNode(0);
            ListNode smalsTail = smalsDumyHead;
            ListNode bigsDumyHead = new ListNode(0);
            ListNode bigsTail = bigsDumyHead;

            ListNode [] ts = new ListNode []{smalsTail,bigsTail};
            process( head, x, ts);

            ts[0].next = bigsDumyHead.next;
            ts[1].next = null; // note
            return smalsDumyHead.next;
        }

        // beats 5.06% of java submissions on Feb 10, 2016
        public ListNode partition2(ListNode head, int x) {
            ListNode smalsDumyHead = new ListNode(0);
            ListNode smalsTail = smalsDumyHead;
            ListNode bigsDumyHead = new ListNode(0);
            ListNode bigsTail = bigsDumyHead;

            ListNode cur = head;
            while (cur != null) {
                if (cur.val < x) {
                    smalsTail.next = cur;
                    smalsTail = smalsTail.next;
                } else {
                    bigsTail.next = cur;
                    bigsTail = bigsTail.next;
                }
                cur = cur.next;
            }

            smalsTail.next = bigsDumyHead.next;
            bigsTail.next = null; // note
            return smalsDumyHead.next;
        }
    }
}

@@ -605,16 +605,18 @@
 nse.%0A//%0A
+%0A%0A
 /*%0AGiven
@@ -904,16 +904,64 @@
 %3E5.%0A */%0A
+// https://leetcode.com/problems/partition-list/
 %0Apublic 
@@ -1142,16 +1142,20 @@
 Node%5B%5D t
+Node
 s) %7B%0A   
@@ -1232,32 +1232,36 @@
                t
+Node
 s%5B0%5D.next = node
@@ -1287,15 +1287,24 @@
    t
+Node
 s%5B0%5D =
-t
+ tNode
 s%5B0%5D
@@ -1348,32 +1348,36 @@
                t
+Node
 s%5B1%5D.next = node
@@ -1403,16 +1403,20 @@
    t
+Node
 s%5B1%5D = t
 s%5B1%5D
@@ -1411,16 +1411,20 @@
 s%5B1%5D = t
+Node
 s%5B1%5D.nex
@@ -1451,32 +1451,33 @@
 %0A               
+ 
 process(node.nex
@@ -1479,24 +1479,28 @@
 e.next, x, t
+Node
 s);%0A        
@@ -1508,32 +1508,53 @@
    %7D%0A        %7D%0A%0A
+        // recursion%0A
         public L
@@ -1821,13 +1821,19 @@
 Node
- 
 %5B%5D t
+ailNode
 s = 
@@ -1844,17 +1844,16 @@
 ListNode
- 
 %5B%5D%7Bsmals
@@ -1857,16 +1857,17 @@
 alsTail,
+ 
 bigsTail
@@ -1889,17 +1889,16 @@
 process(
- 
 head, x,
@@ -1899,16 +1899,23 @@
 ad, x, t
+ailNode
 s);%0A%0A   
@@ -1924,16 +1924,23 @@
        t
+ailNode
 s%5B0%5D.nex
@@ -1975,16 +1975,23 @@
        t
+ailNode
 s%5B1%5D.nex
@@ -2109,32 +2109,48 @@
 on Feb 10, 2016%0A
+        // loop%0A
         public L
@@ -2386,32 +2386,69 @@
  bigsDumyHead;%0A%0A
+            // divide it into 2 list%0A
             List
@@ -2792,32 +2792,86 @@
 %0A            %7D%0A%0A
+            // append the bigger list to smaller list%0A
             smal

Add comments to Leetcode86PartitionList