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}.

基本思路：     用了一个很蠢很直接的方法，定位到中间节点，后半段入栈，然后把后半段与前半段拼接组成新链表

 /**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) { val = x; }

  * }

  */

 public class Solution {

     public void reorderList(ListNode head) {

           if (head == null)

             return;

           ListNode node = head.next;

           int len = 0;

           while(node != null){

               len ++;

               node = node.next;

           }

           System.out.println("len:"+len);

           if(len == 2){

               ListNode temp = head.next;

               head.next = temp.next;

               temp.next = null;

               head.next.next = temp;

               return;

           }else if(len == 1 || len == 0){

               return;

           }

           int isOdd = len % 2;

           if(isOdd == 1){

               int mid = len / 2 + 1;

               Stack<ListNode> stack = new Stack();

               int j = 1;

               ListNode midNode = head.next;

               while(j != mid){

                   j++;

                   midNode = midNode.next;

               }

               ListNode realMidNode = midNode;

               midNode = midNode.next;

               j++;

               stack.push(midNode);

               while(j != len){

                   j++;

                   midNode = midNode.next;

                   stack.push(midNode);

               }

               j = 1;

               ListNode leftTemp = head.next;

               ListNode rightTemp = stack.pop();

               rightTemp.next = leftTemp;

               head.next = rightTemp;

                ListNode tail = leftTemp;

               j++;

               while(j < mid){

                   j++;

                   leftTemp = leftTemp.next;

                   rightTemp = stack.pop();

                   rightTemp.next = leftTemp;

                   tail.next = rightTemp;

                   tail = leftTemp;

               }

               tail.next = realMidNode;

               realMidNode.next = null;

           }else{

               int mid = len / 2 ;

               Stack<ListNode> stack = new Stack<>();

               int j = 1;

               ListNode midNode = head.next;

               while(j != mid){

                   j++;

                   midNode = midNode.next;

               }

               j++;

               midNode = midNode.next;

               stack.push(midNode);

               while(j != len){

                   j++;

                   midNode = midNode.next;

                   stack.push(midNode);

               }

               j=1;

               ListNode leftTemp = head.next;

               ListNode rightTemp = stack.pop();

               rightTemp.next = leftTemp;

               head.next = rightTemp;

                ListNode tail = leftTemp;  

               while(j != mid){

                   j++;

                   leftTemp = leftTemp.next;

                   rightTemp = stack.pop();

                   rightTemp.next = leftTemp;

                   tail.next = rightTemp;

                   tail = leftTemp;

               }

               tail.next = null;

           }

     }

 }