reorder-list

package com.niuke.p8;
/**
 * reorder-list
 * @author Administrator
 *
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) {
            return;
        }
        
        //快慢指针
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        //拆分链表，并且反转中间节点之后的链表
        ListNode after = slow.next;
        slow.next = null;
        ListNode pre = null;
        while(after != null) {
            ListNode temp = after.next;
            after.next = pre;
            pre = after;
            after = temp;
        }
        //两个链表合并
        ListNode first = head;
        after = pre;
        while(first != null && after != null) {
            ListNode ftemp = first.next;
            ListNode aftemp = after.next;
            first.next =  after;
            first = ftemp;
            after.next = first;
            after = aftemp;
        }
    }

}