package com.fishercoder.solutions;

import com.fishercoder.common.classes.ListNode;

/**
 * 143. Reorder List
 *
 * Given a singly linked list L: L0→L1→…→Ln-1→Ln,
 reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

 You must do this in-place without altering the nodes' values.

 For example,
 Given {1,2,3,4}, reorder it to {1,4,2,3}.
 */
public class _143 {

    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
		/* first we use two pointers to separate this list into two parts */
        ListNode slowNode = head;
        ListNode fastNode = head;
        while (fastNode.next != null) {
            fastNode = fastNode.next;
            if (fastNode.next != null) {
                fastNode = fastNode.next;
            } else {
                break;
            }
            slowNode = slowNode.next;
        }
        // two sublist heads
        ListNode head1 = head;
        ListNode head2 = slowNode.next;
        // detach the two sublists;
        slowNode.next = null;

        // reverse the second sublist
        ListNode cur = head2;
        ListNode post = cur.next;
        cur.next = null;
        while (post != null) {
            ListNode temp = post.next;
            post.next = cur;
            cur = post;
            post = temp;
        }
        head2 = cur;// the new head of the reversed sublist

        // merge the two sublists as required
        ListNode p = head1;
        ListNode q = head2;
        while (q != null) {
            ListNode temp1 = p.next;
            ListNode temp2 = q.next;
            p.next = q;
            q.next = temp1;
            p = temp1;
            q = temp2;
        }
    }

}

@@ -343,16 +343,56 @@
 _143 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -432,24 +432,28 @@
 ) %7B%0A        
+   
+ 
 if (head == 
@@ -493,16 +493,20 @@
         
+    
 return;%0A
@@ -517,12 +517,26 @@
     
-%7D%0A%09%09
+    %7D%0A            
 /* f
@@ -600,32 +600,36 @@
 arts */%0A        
+    
 ListNode slowNod
@@ -638,32 +638,36 @@
 = head;%0A        
+  
+  
 ListNode fastNod
@@ -668,32 +668,36 @@
 astNode = head;%0A
+    
         while (f
@@ -724,32 +724,36 @@
 ) %7B%0A            
+ 
+   
 fastNode = fastN
@@ -754,32 +754,36 @@
  fastNode.next;%0A
+    
             if (
@@ -815,32 +815,36 @@
                 
+    
 fastNode = fastN
@@ -865,16 +865,20 @@
         
+   
+ 
 %7D else %7B
@@ -894,16 +894,20 @@
         
+    
 break;%0A 
@@ -909,34 +909,42 @@
 ak;%0A            
+  
-%7D%0A
+  %7D%0A    
             slow
@@ -965,34 +965,42 @@
 e.next;%0A        
-%7D%0A
+    %7D%0A    
         // two s
@@ -1012,32 +1012,36 @@
 t heads%0A        
+    
 ListNode head1 =
@@ -1039,32 +1039,36 @@
 e head1 = head;%0A
+    
         ListNode
@@ -1099,16 +1099,20 @@
         
+    
 // detac
@@ -1131,32 +1131,36 @@
 blists;%0A        
+   
+ 
 slowNode.next = 
@@ -1166,16 +1166,20 @@
  null;%0A%0A
+    
         
@@ -1208,32 +1208,36 @@
 sublist%0A        
+  
+  
 ListNode cur = h
@@ -1234,32 +1234,36 @@
 de cur = head2;%0A
+    
         ListNode
@@ -1288,16 +1288,20 @@
         
+ 
+   
 cur.next
@@ -1309,16 +1309,20 @@
 = null;%0A
+    
         
@@ -1348,32 +1348,36 @@
 ) %7B%0A            
+    
 ListNode temp = 
@@ -1395,24 +1395,28 @@
             
+   
+ 
 post.next = 
@@ -1432,16 +1432,20 @@
         
+    
 cur = po
@@ -1456,24 +1456,28 @@
             
+  
+  
 post = temp;
@@ -1477,32 +1477,36 @@
 = temp;%0A        
+    
 %7D%0A        head2 
@@ -1499,16 +1499,20 @@
         
+ 
+   
 head2 = 
@@ -1564,16 +1564,20 @@
         
+    
 // merge
@@ -1606,32 +1606,36 @@
 equired%0A        
+ 
+   
 ListNode p = hea
@@ -1638,16 +1638,20 @@
  head1;%0A
+    
         
@@ -1674,24 +1674,28 @@
 d2;%0A        
+    
 while (q != 
@@ -1706,32 +1706,36 @@
 ) %7B%0A            
+   
+ 
 ListNode temp1 =
@@ -1739,24 +1739,28 @@
 1 = p.next;%0A
+    
             
@@ -1796,16 +1796,20 @@
         
+  
+  
 p.next =
@@ -1812,16 +1812,20 @@
 xt = q;%0A
+    
         
@@ -1856,16 +1856,20 @@
         
+    
 p = temp
@@ -1863,32 +1863,36 @@
      p = temp1;%0A
+    
             q = 
@@ -1898,16 +1898,30 @@
  temp2;%0A
+            %7D%0A
         
@@ -1928,11 +1928,10 @@
 %7D%0A    %7D%0A
-%0A
 %7D%0A

refactor 143