@RestController
@RequestMapping("/api/travel")
public class TravelController {

    private final ChatClient chatClient;

    public TravelController(ChatClient chatClient) {
        this.chatClient = chatClient;
    }

    @GetMapping(value = "/stream", produces = MediaType.TEXT_EVENT_STREAM_VALUE)
    public Flux<Map<String, Object>> streamScenicSpots() {
        String prompt = """
        请依次介绍中国的5个著名景点。
        每个景点单独输出一个JSON对象，不要合并。
        格式如下：
        {"name": "景点名", "desc": "简介"}
        每个景点之间用字符串 <END> 分隔。
        """;

        StringBuilder buffer = new StringBuilder();

        return chatClient.prompt()
                .user(prompt)
                .stream()
                .flatMap(chunk -> {
                    String text = chunk.getOutput().getContent();
                    buffer.append(text);

                    // 按 <END> 分割
                    List<Map<String, Object>> ready = new ArrayList<>();
                    int idx;
                    while ((idx = buffer.indexOf("<END>")) != -1) {
                        String jsonChunk = buffer.substring(0, idx).trim();
                        buffer.delete(0, idx + "<END>".length());
                        try {
                            Map<String, Object> json = new ObjectMapper().readValue(jsonChunk, Map.class);
                            ready.add(json);
                        } catch (Exception e) {
                            // 不完整的JSON先跳过
                        }
                    }

                    // 返回所有完整JSON块
                    return Flux.fromIterable(ready);
                });
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //暴力
    int res = 0;
    long targetSum = 0;
    public int pathSum(TreeNode root, int _targetSum) {
        //暴力搜索，类似于我们 普通前缀和的 两层for循环
        targetSum = (long)_targetSum;
        t1(root);
        return res;
    }
    public void t1(TreeNode root){
        if(root == null) return;
        //起点
        traverse(root, 0);
        t1(root.left);
        t1(root.right);
    }
    public void traverse(TreeNode root,long curSum){
        if(root == null){
            return;
        }
        curSum+=root.val;
        if(curSum == targetSum) res++;
        traverse(root.left, curSum);
        traverse(root.right, curSum);
    }

}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //暴力
    int res = 0;
    long targetSum = 0;
    //只针对单一个数
    //k：前缀和 v：相同前缀和的个数
    Map<Long, Integer> preSumCounter = new HashMap<>();

    public int pathSum(TreeNode root, int _targetSum) {
        //前缀和 + 两数之和
        targetSum = (long) _targetSum;
        preSumCounter.put(0L, 1); // 前缀和为0的次数为1
        traverse(root, 0);
        return res;
    }

    public void traverse(TreeNode root, long curSum) {
        if (root == null) {
            return;
        }
        curSum += root.val;
        // preSum - xx = targetSum
        // preSum - targetSum = xx
        //即在map里找是否有 树为 presum + (-targetSum)
        res += preSumCounter.getOrDefault(curSum + (-targetSum), 0);
        //更新前缀和
        preSumCounter.put(curSum, preSumCounter.getOrDefault(curSum, 0) + 1);

        traverse(root.left, curSum);
        traverse(root.right, curSum);
        
        //回退
        preSumCounter.put(curSum, preSumCounter.get(curSum) - 1);
    }

}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }
    public int dfs(TreeNode cur){
        if(cur == null) return 0;
        int leftSum = dfs(cur.left);
        int rightSum = dfs(cur.right);
        //子树的返回
        int ret = Math.max(cur.val, Math.max(leftSum,rightSum) + cur.val);
        //最终结果
        res = Math.max(res, Math.max(ret, cur.val + leftSum + rightSum));
        return ret;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //法一 dfs
        return dfs(root, p, q);
    }

    public TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        if (root == p || root == q)
            return root;
        TreeNode left = dfs(root.left, p, q);
        TreeNode right = dfs(root.right, p, q);
        if (left == null)
            return right;
        if (right == null)
            return left;
        if (left == right)
            return root;
        //p,q都没找到
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //k：子节点 v：父节点
    Map<TreeNode, TreeNode> map = new HashMap<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, null);
        //q节点的祖先 集合
        Set<TreeNode> qZX = new HashSet<>();
        while (q != null) {
            qZX.add(q);
            q = map.get(q);
        }

        while (p != null) {
            //相交节点
            if (qZX.contains(p)) {
                return p;
            }
            p = map.get(p);
        }
        return null;
    }

    //
    public void dfs(TreeNode cur, TreeNode par) {
        if (cur == null) {
            return;
        }
        map.put(cur, par);
        dfs(cur.left, cur);
        dfs(cur.right, cur);
    }
}

class Solution {
	public boolean isSymmetric(TreeNode root) {
		if(root==null) {
			return true;
		}
		//调用递归函数，比较左节点，右节点
		return dfs(root.left,root.right);
	}
	
	boolean dfs(TreeNode left, TreeNode right) {
		//递归的终止条件是两个节点都为空
		//或者两个节点中有一个为空
		//或者两个节点的值不相等
		if(left==null && right==null) {
			return true;
		}
		if(left==null || right==null) {
			return false;
		}
		if(left.val!=right.val) {
			return false;
		}
		//再递归的比较 左节点的左孩子 和 右节点的右孩子
		//以及比较  左节点的右孩子 和 右节点的左孩子
		return dfs(left.left,right.right) && dfs(left.right,right.left);
	}
}

作者：王尼玛
链接：https://leetcode.cn/problems/symmetric-tree/solutions/46560/dong-hua-yan-shi-101-dui-cheng-er-cha-shu-by-user7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        return dfs(root);
    }

    public TreeNode dfs(TreeNode root) {
        if (root == null)
            return null;
        TreeNode left = dfs(root.left);
        TreeNode right = dfs(root.right);
        //在根节点 交换左右子节点即可
        root.left = right;
        root.right = left;

        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //int cnt = 0;
    int res = Integer.MIN_VALUE;
    public int maxDepth(TreeNode root) {
        if(root != null){
            dfs(root,1);
            return res;
        }
        return 0;
    }
    public void dfs(TreeNode root,int cnt){
        if(root == null) {
            return ;
        }
        if(root.left == null && root.right == null){
            res = Math.max(res,cnt);
            return;
        }
        dfs(root.left,cnt + 1);
        dfs(root.right,cnt + 1);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        ArrayDeque<TreeNode> q = new ArrayDeque();
        if (root != null)
            q.add(root);
        int depth = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size > 0) {
                TreeNode cur = q.remove();
                if (cur.left != null) {
                    q.add(cur.left);
                }
                if (cur.right != null) {
                    q.add(cur.right);
                }
                size--;
            }
            depth++;
        }
        return depth;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }
    //也是站在当前根节点 思考 左右子节点要给我返回什么
    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int lM = dfs(root.left);
        int rM = dfs(root.right);
        res = Math.max(lM + rM, res);
        // 这个 1 是指Cur节点返回给上一级的时候，要把cur节点 加上去
        return Math.max(lM, rM) + 1;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList();

    public boolean isValidBST(TreeNode root) {
        f1(root);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) <= list.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
    //二叉搜索树 中序遍历 为 单调递增数组
    public void f1(TreeNode root) {
        if (root == null) {
            return;
        }
        f1(root.left);
        list.add(root.val);
        f1(root.right);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    StringBuilder serRes = new StringBuilder();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        f1(root);
        return serRes.toString();
    }
    public void f1(TreeNode root){
        if(root == null){
            serRes.append("null,");
            return;
        }
        else serRes.append(root.val + ",");
        f1(root.left);
        f1(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String []datas = data.split(",");
        return builder(datas);
    }
    //构建树
    int index = 0;

    public TreeNode builder(String[] data){
        //看示例1 即 从上到下，从右倒左遍历
        String curV = data[index];
        index++;
        //当前节点
        TreeNode curNode = null;
        if(curV.equals("null")){
            return curNode;
        } 
        else {
            int curVN = Integer.parseInt(curV);
            curNode = new TreeNode(curVN);
            //左右子节点 交给子树去构造，相信递归
            curNode.left = builder(data);
            curNode.right = builder(data);
        }

        return curNode;

    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    StringBuilder serRes = new StringBuilder();

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            if (cur != null) {
                serRes.append(cur.val).append(",");
                q.add(cur.left);
                q.add(cur.right);
            } else {
                serRes.append("null,");
            }
        }
        return serRes.toString();

    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        String[] datas = data.split(",");

        return builder(datas);
    }

    //构建树
    public TreeNode builder(String[] data) {

        if (data.length == 0 || data[0].equals("null")) {
            return null;
        }
        TreeNode res = new TreeNode(Integer.parseInt(data[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(res);
        int index = 1;
        while (!q.isEmpty()) {
            TreeNode curNode = q.poll();
            if (!data[index].equals("null")) {
                curNode.left = new TreeNode(Integer.parseInt(data[index]));
                q.add(curNode.left);
            }
            index++;
            if (!data[index].equals("null")) {
                curNode.right = new TreeNode(Integer.parseInt(data[index]));
                q.add(curNode.right);
            }
            index++;
        }
        return res;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode pre=null;
    public void flatten(TreeNode root) {
        if(root==null) return;

        if(pre!=null){
            pre.right=root;
        }
        //提前保存一下即可，防止丢失子树
        TreeNode tmp=root.right;
        pre=root;
        flatten(root.left);
        flatten(tmp);
        root.left=null;
    }
}

class Solution {
    public int numTrees(int n) {
        //1: 1
        //2: 2
        //3: 5
        //dp数组含义：n = i时有多少种二叉搜索树

        ////如果整数1 ~ n中的 k 作为根节点值，则 1 ~ k-1 会去构建左子树，k+1 ~ n 会去构建右子树。!!!
        if( n <= 2) return n;
        int []dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2;i <= n;i++){
            //在 i 范围内，当前节点val = k 
            //如果整数1 ~ i中的 k 作为根节点值，则 1 ~ k-1 会去构建左子树，k+1 ~ i 会去构建右子树。!!!
            //此时 
            for(int k = 0;k <= i - 1;k++){
                //左 和 右 组合
                //为什么组合这里是乘法？
                dp[i] += dp[k] * dp[i - k - 1]; 
            }
        }
        return dp[n];
    }
}

class Trie {
    private static class Node {
        Node[] son = new Node[26];
        boolean end = false;
    }

    private final Node root = new Node();

    public Trie() {

    }

    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            //无路可走？ new 出来
            if (cur.son[index] == null) {
                cur.son[index] = new Node();
            }
            cur = cur.son[index];
        }
        cur.end = true;
    }

    public boolean search(String word) {
        return find(word) == 2;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != 0;
    }

    public int find(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (cur.son[index] == null)
                return 0;
            cur = cur.son[index];
        }
        //2为找到了 1为找到前缀
        return cur.end ? 2 : 1;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> l = new ArrayList();
    int index = 0;
    public TreeNode convertBST(TreeNode root) {
        traverse(root);
        //System.out.println(l);
        //每个节点 node 的新值  等于  原树中大于或等于 node.val 的值之和
        int sum = 0;
        for(int i = 0;i < l.size(); i++){
            sum += l.get(i);
        }
        int preSum = 0;
        for(int i = 0; i < l.size(); i++){
            int temp = l.get(i);
            l.set(i, sum - preSum);
            preSum += temp;
        }
        generate(root);
        //System.out.println(l);
        return root;
    }
    public void traverse(TreeNode root){
        if(root == null) return;
        traverse(root.left);
        l.add(root.val);
        traverse(root.right);
    }
    public void generate(TreeNode root){
        if(root == null) return;
        generate(root.left);
        root.val = l.get(index); 
        index++;
        generate(root.right);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        dfs(root1, root2);
        return root1;
    }
    public void dfs(TreeNode root1,TreeNode root2){
        if(root1 == null && root2 == null){
            return;
        }
        else if(root1 == null && root2 != null){
            root1 = root2;
            return;
        }
        else if(root1 != null && root2 == null){
            
            return;
        }
        else if(root1 != null && root2 != null){
            root1.val += root2.val;
        }
        dfs(root1.left,root2.left);
        dfs(root1.right,root2.right);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return build(root1, root2);
    }
    //返回节点
    public TreeNode build(TreeNode root1, TreeNode root2){
        if(root1 == null && root2 == null){
            return null;
        }
        if(root1 != null && root2 == null){
            return root1;
        }
        if(root1 == null && root2 != null){
            return root2;
        }
        
        TreeNode res = new TreeNode();
        if(root1 != null && root2 != null) res.val = root1.val + root2.val; 
        res.left = build(root1.left, root2.left);
        res.right = build(root1.right, root2.right);

        return res;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int l = 0, r = 0;
        List<Integer> res = new ArrayList<>();
        Deque<Integer> dq = new ArrayDeque<>(); // 单调队列，存下标，保持递减

        for (; r < nums.length; r++) {
            // 移除队尾比当前元素小的下标
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[r]) {
                dq.pollLast();
            }
            dq.offerLast(r);

            // 当窗口长度 >= k
            if (r - l + 1 < k) {
                continue; 
            }
            // 队头就是最大值
            res.add(nums[dq.peekFirst()]);

            // 移除队头已经滑出窗口的下标
            if (!dq.isEmpty() && dq.peekFirst() == l) {
                dq.pollFirst();
            }

            l++;
        }

        return res.stream().mapToInt(Integer::intValue).toArray();
    }

}

class Solution {
    public static Random random = new Random();
    public int[] sortArray(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }
    public void sort(int []nums, int l, int r){
        if( l >= r) return;

       int indexX = partition(nums, l, r);
       //l....indexX
       sort(nums, l ,indexX - 1);
       //indeX...r
       sort(nums, indexX + 1, r);
    }
    public int partition(int []nums, int l, int r){
        int i = l + random.nextInt( r - l + 1);
        int x = nums[i];
        swap(nums, l, i);
        int curL = l + 1;
        int curR = r;
        while(true){
            while(curL <= curR && nums[curL] < x){
                curL++;
            }
            while(curL <= curR && nums[curR] > x){
                curR--;
            }
            if(curL >= curR) break;

            swap(nums, curL, curR);
            curL++;
            curR--;
        }
        swap(nums, l, curR);

        return curR;
    }
    public void swap(int []nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public int[] sortArray(int[] nums) {
        int max = 50001;
        int min = -50001;

        int[] counter = new int[max - min + 1];
        for (int num : nums) {
            counter[num - min]++;
        }
        int index = 0;
        //index 为 数组值 value为 数组值的个数
        for (int i = min; i <= max; i++) {
            int cnt = counter[i - min];
            // cnt > 0说明存在
            while (cnt > 0) {
                nums[index] = i;
                cnt--;
                index++;
            }
        }
        return nums;
    }
}

class Solution {
    public int[] sortArray(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }
    //归并排序
    public void sort(int []nums, int l, int r){
        if(l >= r) return;
        int mid = l + (r - l) / 2;
        sort(nums, l, mid);
        sort(nums, mid + 1, r);
        //合并 [l...mid] [mid + 1....r]
        merge(nums, l, mid, mid + 1, r);
    }
    public void merge(int []nums, int s1, int e1, int s2, int e2){
        // [s1...e1] [s1 ... e2]
        int i = s1;
        int j = s2;
        // [2,4] [1,5]
        // [1,2,4,]
        int []temp = new int[e2 - s1 + 1];
        int n = temp.length;
        int k = 0;
        while(i <= e1 || j <= e2){
            while( i > e1 && j <= e2){
                temp[k] = nums[j];
                k++;
                j++;
            }
            while(j > e2 && i <= e1){
                temp[k] = nums[i];
                k++;
                i++;
            }
            if(k >= n) break;
            //谁小谁先移动
            if(nums[i] > nums[j]){
                temp[k] = nums[j];
                k++;
                j++;
            }
            else {
                temp[k] = nums[i];
                k++;
                i++;
            }
        }
        System.arraycopy(temp, 0, nums, s1, temp.length);
        
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public List<Integer> lexicalOrder(int n) {
        //256
        // 1 10 100 101...109 11
        List<Integer> res = new ArrayList();
        for (int i = 0, j = 1; i < n; i++) {
            res.add(j);
            if (j * 10 <= n) {
                j = j * 10;
            } else {
                // 1 10 100 101...109 11 or  1,2 
                // 109 -> 11 ,2 -> 3
                while (j % 10 == 9 || j + 1 > n) {
                    j = j / 10;
                }
                j++;
            }
        }
        return res;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return sort(head);
    }

    //从中间分开
    public ListNode divide(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        pre.next = null;
        return slow;
    }

    //归并排序
    public ListNode sort(ListNode head1) {
        if (head1 == null || head1.next == null) {
            return head1;
        }
        //拆成两部分，并返回后部门的头结点
        ListNode head2 = divide(head1);
        //mid(4→2→1→3)   ---> 分成两部分
        //head1: 4 → 2 → null
        //head2: 1 → 3 → null
        head1 = sort(head1);

        head2 = sort(head2);

        return merge(head1, head2);
    }

    //两链表合并，要有序
    // head1 .... 
    // head2 ....
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode res = new ListNode();
        ListNode cur = res;
        while (head1 != null || head2 != null) {
            if (head2 == null) {
                cur.next = head1;
                break;
            }
            if (head1 == null) {
                cur.next = head2;
                break;
            }
            if (head1.val > head2.val) {
                cur.next = head2;
                head2 = head2.next;
            } else {
                cur.next = head1;
                head1 = head1.next;
            }
            cur = cur.next;
        }
        return res.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        //最小堆，堆顶为最小值
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        //先将最小的放进来
        for(ListNode head: lists){
            if(head == null) continue;
            pq.add(head);
        }
        ListNode dummyHead = new ListNode();
        ListNode res = dummyHead;
        
        while(!pq.isEmpty()){
            ListNode minNode = pq.poll();
            res.next = minNode;
            res = res.next;
            if(minNode.next != null){
                pq.add(minNode.next);
            }
        }
        return dummyHead.next;
    }
}