题目

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

解

class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null){
            return ;
        }

        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
            if(fast != null){
                fast = fast.next;
            }
        }

        ListNode head2 = slow.next;
        slow.next = null;

        ListNode head4 = reverse(head2);
        ListNode head3 = head;
      
     
        while(head3 != null && head4 != null){
            ListNode p1= head3.next;
            ListNode p2 = head4.next;
            
            head3.next = head4;
            head4.next = p1;

            head3 = p1;
            head4 = p2;
        }
    }

    public ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }

        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while(cur != null){
            next = cur.next;

            cur.next = pre;

            pre = cur;
            cur = next;
        }
        return pre;
    }
}