class ShuffleLinkedList {

    public Node shuffle(Node list) {//TIME : O (N LOG N), SPACE : O (LOG N)
        if (list == null || list.next == null) return list;
        //split half
        Node slow = list, fast = list.next;
        int preL = 1;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            preL++;
            fast = fast.next.next;
        }
        int postL = preL;
        if (fast == null) {
            postL--;
        }
        Node post = slow.next, pre = list;
        slow.next = null;
        return merge(shuffle(pre),preL,shuffle(post),postL);
    }

}