LintCode: 99. 重排链表

题目：

分析：

首先想到将链表L按照这个规律重新赋值一遍，但题中说不能改变结点的值，然后想到将链表反转后重新链接起来。

以1->2->3->4为例

按虚线走，形成1->4->2->3->3->2->4->1，若是节点的值都不相同，则遇到相同时，就可以断开形成，若是有相同结点的值，也可以先统计结点个数，然后判断终止条件。但这样就需要新建一个链表。所以想到将链表一分为二，反转后半段，然后重新链接起来，依旧是1->4->2->3.

这样思路就来了：

1. 将链表一分为二，找到中间结点。用到快慢指针。1->2->3->4，偶数个数点中间mid结点为2；1->2->3->4->5，奇数个数点中间mid结点为3。
2. 反转mid结点之后的所有结点。
3. 将两链表链接起来。

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: nothing
     */
    public void reorderList(ListNode head) {
        // write your code here
        if(head==null)  return;
        ListNode mid=findMid(head);
        ListNode head2=reverse(mid.next);
        mid.next=null;  //把前半段最后一个节点的next结点置为null；
        merge(head,head2);
    }

    public ListNode reverse(ListNode head){
        ListNode newHead=null;
        while(head!=null){
            ListNode temp=head.next;
            head.next=newHead;
            newHead=head;
            head=temp;
        }
        return newHead;
    }

    public void merge(ListNode head1,ListNode head2){
        int index=0;
        ListNode temp=new ListNode(0);
        while (head1!=null && head2!=null){
            if(index%2==0){
                temp.next=head1;
                head1=head1.next;
            }else{
                temp.next=head2;
                head2=head2.next;
            }
            temp=temp.next;
            index++;
        }
        if(head1==null){
            temp.next=head2;
        }
        if(head2==null){
            temp.next=head1;
        }
    }

    //找到中间结点
    public ListNode findMid(ListNode head){
        ListNode slow=head;ListNode fast=head.next;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}