链表的重排序

import java.util.*;
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;
        //(1)快慢指针找到中间节点
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null&&fast.next.next!=null)
        {
             fast=fast.next.next;
             slow=slow.next;
        }

        //(2)拆分链表,并且反转后面一部分链表
        ListNode after=slow.next;
        slow.next=null;
        //ListNode pre=reverseList(after);
        ListNode pre=null;
        while(after!=null){

             ListNode tmp=after.next;
             after.next=pre;
             pre=after;
             after=tmp;
        }

        //(3)合并两个链表
        ListNode first=head;
        after=pre;
        while(first!=null&&after!=null){
            ListNode ftemp=first.next;
            ListNode atemp=after.next;
            first.next=after;
            first=ftemp;
            after.next=first;
            after=atemp;
        }

    }

    //遍历链表
    public void printList(ListNode head)
    {
         while(head!=null)
         {
             System.out.print(head.val+" ");
             head=head.next;
         }
         System.out.println();
    }
    public static void main(String[]args){
        // System.out.println("Hello World!");
         ListNode head=new ListNode();
         head.next=new ListNode();
         head.next.next=new ListNode();
         Solution s=new Solution();
         s.reorderList(head);
         s.printList(head);

    }

}