public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast != null) {
                slow = slow.next;
            }
        }

        ListNode prev = slow.next;
        slow.next = null;
        ListNode cur = null;
        //reverse second half of the list
        while (prev != null) {
            ListNode next = prev.next;
            prev.next = cur;
            cur = prev;
            prev = next;
        }

        ListNode first = head;
        ListNode second = cur;
        while (first != null && second != null && first != second) {
            ListNode tmp = second.next;
            second.next = first.next;
            first.next = second;

            first = second.next;
            second = tmp;
        }
    }