private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode n = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                n.next = left;
                left = left.next;
            } else {
                n.next = right;
                right = right.next;
            }
            n = n.next;
        }
        n.next = left != null ? left : right;
        return dummy.next;
    }