重拍链表java实现

算法题目：
将给定的单链表 L\ L
L： L0→L1→…→Ln−1→LnL_0→L_1→…→L_{n-1}→L_ nL0​→L1​→…→Ln−1​→Ln​
重新排序为：
L0→Ln→L1→Ln−1→L2→Ln−2→…L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…L0​→Ln​→L1​→Ln−1​→L2​→Ln−2​→…
要求使用原地算法，不能改变节点内部的值，需要对实际的节点进行交换。
例如：
对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}.

解决这道题只需要三步
第一步：找到链表中间位置，将链表分为两部分
第二步：将右边链表反转
第三步：按照要求将左右两条链表合并
下面举例说明：

附上代码，我将三步封装成了三个方法：看起来比较清晰

 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;
        }
        ListNode mid=getMid(head);
        ListNode h2=null;
        h2=mid.next;
        mid.next=null;
        ListNode h1=head;
        //反转h2
        h2=reverseNode(h2);
        //合并h1&h2
        mergeNode(h1,h2);
    }
    //查找中间节点
    public ListNode getMid(ListNode head){
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    //反转链表
    public ListNode reverseNode(ListNode head){
        ListNode node=head;
        ListNode cur=head.next;
        head.next=null;
        ListNode next=null;
        while(cur!=null){
            next=cur.next;
            cur.next=node;
            node=cur;
            cur=next;
        }
        return node;
    }
    //合并链表
    public void mergeNode(ListNode h1,ListNode h2){
        ListNode next=null;//保存h2的下一个节点
        while(h1!=null&&h2!=null){
            next=h2.next;
            h2.next=h1.next;
            h1.next=h2;
            h1=h2.next;
            h2=next;
        }
    }
}