public void reOrderArray(int[] array) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) {
                list1.add(array[i]);
            } else {
                list2.add(array[i]);
            }
        }
        list1.addAll(list2);
        for (int i = 0; i < array.length; i++) {
            array[i] = list1.get(i);
        }
    }

    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        if (k == 0) {
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        list.add(head);
        ListNode cur = head;
        while (cur.next != null) {
            list.add(cur.next);
            cur = cur.next;
        }
        if (k > list.size()) {
            return null;
        }
        return list.get(list.size() - k);
    }


    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        list.add(head);
        ListNode cur = head;
        while (cur.next != null) {
            list.add(cur.next);
            cur = cur.next;
        }
        head.next = null;
        for (int i = 1; i < list.size(); i++) {
            list.get(i).next = list.get(i - 1);
        }
        return list.get(list.size() - 1);
    }

    public static ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1 == null && list2 == null) {
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        while (cur1 != null || cur2 != null) {
            if (cur1 == null) {
                list.add(cur2);
                cur2 = cur2.next;
                continue;
            }
            if (cur2 == null) {
                list.add(cur1);
                cur1 = cur1.next;
                continue;
            }
            if (cur1.val < cur2.val) {
                list.add(cur1);
                cur1 = cur1.next;
                continue;
            }
            if (cur1.val >= cur2.val) {
                list.add(cur2);
                cur2 = cur2.next;
                continue;
            }
        }
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).next = list.get(i + 1);
        }
        return list.get(0);
    }


    public static boolean HasSimTree(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null && root2 != null) {
            return false;
        }
        if (root1.val == root2.val) {
            return HasSimTree(root1.left, root2.left) && HasSimTree(root1.right, root2.right);
        }
        return false;

    }

    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        boolean flag = false;
        if (root1.val == root2.val) {
            flag = HasSimTree(root1, root2);
        }
        return flag || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        Mirror(root.left);
        Mirror(root.right);
    }

    //输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
    // 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
    public static ArrayList<Integer> printMatrix(int[][] matrix) {
        if (matrix.length == 0) {
            return null;
        }
        ArrayList<Integer> list = new ArrayList<>();
        if (matrix.length == 1) {
            for (int i = 0; i < matrix[0].length; i++) {
                list.add(matrix[0][i]);
            }
            return list;
        }
        if (matrix[0].length == 1) {
            for (int i = 0; i < matrix.length; i++) {
                list.add(matrix[i][0]);
            }
            return list;
        }
        int[][] map = new int[matrix.length + 2][matrix[0].length + 2];
        //初始化地图
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (i == 0 || j == 0 || i == map.length - 1 || j == map[0].length - 1) {
                    map[i][j] = 1;
                } else {
                    map[i][j] = 0;
                }
            }
        }
        for (int i = 1; i < map.length - 1; ) {
            for (int j = 1; j < map[0].length - 1; ) {
                if (map[i][j] == 0) {
                    list.add(matrix[i - 1][j - 1]);
                    map[i][j] = 1;
                }
                //如果右边有
                if (map[i][j + 1] == 0 && map[i - 1][j] == 1) {
                    j++;
                    continue;
                }
                //下边有
                if (map[i + 1][j] == 0) {
                    i++;
                    continue;
                }
                //左边
                if (map[i][j - 1] == 0) {
                    j--;
                    continue;
                }
                if (map[i - 1][j] == 0) {
                    i--;
                    continue;
                }
                if (map[i + 1][j] == 1 && map[i][j + 1] == 1 && map[i - 1][j] == 1 && map[i][j - 1] == 1) {
                    break;
                }

            }
            break;
        }
        return list;
    }