package com.fishercoder.solutions;

import com.fishercoder.common.classes.ListNode;

/**
 * 86. Partition List
 *
 * 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 _86 {

  public static class Solution1 {
    public ListNode partition(ListNode head, int x) {
      if (head == null || head.next == null) {
        return head;
      }
      ListNode left = new ListNode(0);
      ListNode right = new ListNode(0);
      ListNode less = left;
      ListNode greater = right;
      while (head != null) {
        if (head.val < x) {
          less.next = head;
          less = less.next;
        } else {
          greater.next = head;
          greater = greater.next;
        }
        head = head.next;
      }
      greater.next = null;
      less.next = right.next;
      return left.next;
    }
  }
}

@@ -236,17 +236,18 @@
 l to x.%0A
-%0A
+ *
  You sho
@@ -331,17 +331,18 @@
 itions.%0A
-%0A
+ *
  For exa
@@ -347,16 +347,18 @@
 xample,%0A
+ *
  Given 1
@@ -384,16 +384,18 @@
  x = 3,%0A
+ *
  return 
@@ -438,16 +438,18 @@
 86 %7B%0A%0A  
+ 
+ 
 public s
@@ -472,16 +472,20 @@
 tion1 %7B%0A
+    
     publ
@@ -532,24 +532,30 @@
  x) %7B%0A      
+     
+ 
 if (head == 
@@ -575,32 +575,40 @@
 next == null) %7B%0A
+        
         return h
@@ -614,26 +614,38 @@
 head;%0A      
+  
-%7D%0A
+    %7D%0A      
       ListNo
@@ -663,32 +663,38 @@
 ew ListNode(0);%0A
+      
       ListNode r
@@ -715,32 +715,38 @@
 tNode(0);%0A      
+     
+ 
 ListNode less = 
@@ -751,16 +751,22 @@
 = left;%0A
+      
       Li
@@ -795,16 +795,22 @@
 ;%0A      
+   
+   
 while (h
@@ -816,32 +816,40 @@
 head != null) %7B%0A
+        
         if (head
@@ -856,24 +856,34 @@
 .val %3C x) %7B%0A
+          
           le
@@ -890,32 +890,42 @@
 ss.next = head;%0A
+          
           less =
@@ -944,16 +944,24 @@
         
+ 
+       
 %7D else %7B
@@ -967,24 +967,34 @@
 %7B%0A          
+   
+       
 greater.next
@@ -1008,24 +1008,34 @@
 ;%0A          
+    
+      
 greater = gr
@@ -1046,34 +1046,50 @@
 r.next;%0A        
+    
-%7D%0A
+    %7D%0A        
         head = h
@@ -1104,24 +1104,36 @@
 ;%0A      
-%7D%0A
+      %7D%0A   
       
+   
 greater.
@@ -1147,24 +1147,30 @@
 null;%0A      
+   
+   
 less.next = 
@@ -1183,24 +1183,30 @@
 next;%0A      
+  
+    
 return left.
@@ -1215,16 +1215,22 @@
 xt;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 86