[leetcode]

问题：Given a singly linked list L: L0→L1→…→Ln-1→Ln
,reorder it to: L0→Ln→L1→Ln-1→L2→L*n-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}.

思路：我们发现这种混合体有一个特点，就是单数是从头开始数的节点，双数是从尾开始数的节点，因为是单向链表，所以只有next没有previous，因此颠倒的任务只能交给数据结构来完成，无疑栈就是为此而生的，先进后出。
使用辅助栈的答案：

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if (head==null||head.next==null)
            return;
        int count=0;
        ListNode test=head;
        while (test!=null)
        {
            count++;
            test=test.next;
        }
        if (count%2==0)
        {
            ListNode head1=head;
            ListNode head2=head;
            ListNode duandian=head;
            for (int i=0;i<count/2;i++)
            {
                head2=head2.next;
            }
            for (int i=0;i<count/2-1;i++)
            {
                duandian=duandian.next;
            }
            duandian.next=null;
            Stack<ListNode>stack1=new Stack<ListNode>();
            while (head2!=null)
            {
                ListNode t=head2;
                stack1.push(t);
                head2=head2.next;
            }
            while (!stack1.empty()&&head1!=null)
            {
                ListNode n=stack1.pop();
                n.next=head1.next;
                head1.next=n;
                head1=n.next;
            }
        }
        else
        {
            ListNode head1=head;
            ListNode head2=head.next;
            ListNode duandian=head;
            for (int i=0;i<count/2;i++)
            {
                head2=head2.next;
            }
            for (int i=0;i<count/2;i++)
            {
                duandian=duandian.next;
            }
            duandian.next=null;
            Stack<ListNode>stack1=new Stack<ListNode>();
            while (head2!=null)
            {
                ListNode t=head2;
                stack1.push(t);
                head2=head2.next;
            }
            while (!stack1.empty()&&head1.next!=null)
            {
                ListNode n=stack1.pop();
                n.next=head1.next;
                head1.next=n;
                head1=n.next;
            }
        }
    }
}

不使用辅助栈的答案：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.Stack;
public class Solution {
    public void reorderList(ListNode head) {
       if(head==null)
                return;
            ListNode slow=head;
            ListNode fast=head;
            while(fast.next!=null&&fast.next.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }
            ListNode pre=slow.next;
            if(pre!=null&&pre.next!=null){
                ListNode nex=pre.next;
                while(nex!=null){
                pre.next=nex.next;
                nex.next=slow.next;
                slow.next=nex;
                nex=pre.next;
               }       
            }    
            merge(head,slow);
        }
        public static void merge(ListNode head,ListNode slow){
            ListNode p=head;
            ListNode q=slow.next;
            while(q!=null&&p!=null){
                slow.next=q.next;
                q.next=p.next;
                p.next=q;
                q=slow.next;
                p=p.next.next;
            }
        }
}