leetcode

public class TestClass {
    public static void main(String[] agrs) {
        List<ListNode> listNodes = new ArrayList<>();
    }

    //快速排序
    public void quickSort(int arr[], int head, int tail) {
        if (head > tail) {
            return;
        }
        int result = arr[head];
        int i = head;
        int j = tail;
        while (i < j) {
            while (arr[i] <= result && i < j) {
                i++;
            }
            while (arr[j] >= result && j > i) {
                j--;
            }
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        if (i == j) {
            arr[head] = arr[i];
            arr[i] = result;
        }
        quickSort(arr, head, i - 1);
        quickSort(arr, i + 1, tail);
    }

    //删除链表第N个节点
    public ListNode deleteNNode(ListNode mTreeNode, int n) {
        ListNode head = new ListNode(0);
        head.next = mTreeNode;
        ListNode first = head;
        ListNode second = head;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return head.next;
    }

    //删除链表第N个节点
    public ListNode deleteN2Node(ListNode mTreeNode, int n) {
        ListNode head = new ListNode(0);
        head.next = mTreeNode;
        ListNode first = head;
        ListNode second = head;
        int count = 0;
        while (first != null) {
            first = first.next;
            count++;
        }
        for (int i = 0; i < count - n; i++) {
            second = second.next;
        }
        second.next = second.next.next;
        return head;
    }

    //合并两个链表
    public ListNode conbineTreeNode(ListNode first, ListNode second) {
        ListNode treeNode = new ListNode(0);
        ListNode temp = treeNode;
        while (first != null && second != null) {
            int val = first.val;
            int result = second.val;
            if (val < result) {
                temp.next = first;
                first = first.next;
            } else {
                temp.next = second;
                second = second.next;
            }
            temp = temp.next;
        }
        if (first == null) {
            temp.next = second;
        } else {
            temp.next = first;
        }
        return treeNode.next;
    }

    //两两交换链表节点 1-2-3-4-5-6  2-1-4-3-6-5  递归思想
    public ListNode changeTwoNodeByRec(ListNode mTreeNode) {
        if (mTreeNode == null && mTreeNode.next == null) {
            return mTreeNode;
        }
        ListNode node = mTreeNode.next;
        mTreeNode.next = changeTwoNodeByRec(node.next);
        node.next = mTreeNode;
        return mTreeNode;
    }

    //旋转单链表 1-2-3-4  4-3-2-1
    public ListNode reverseTreeNode(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = prev;
            prev = head;
            head = tmp;
        }
        return prev;
    }

    //递归旋转单链表
    public ListNode reverseTreeNodeByRec(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode treeNode = reverseTreeNodeByRec(head.next);
        head.next.next = head;
        head.next = null;
        return treeNode;
    }

    //链表向右移动n个节点,先闭环，再断节点 1-2-3-4 n = 2 --------> 3-4-1-2
    public ListNode removeTreeNode(ListNode head, int n) {
        //先整体闭合成环
        ListNode node = head;
        int count = 1;
        while (node.next != null) {
            node = node.next;
            count++;
        }
        node.next = head;
        ListNode tail = head;
        for (int i = 0; i < n - n % count - 1; i++) {
            tail = tail.next;
        }
        ListNode newHead = tail.next;
        tail.next = null;
        return newHead;
    }

    //删除链表中的连续重复节点 1-2-3-3  1-2
    public ListNode deleteDucliteNode(ListNode head) {
        ListNode dump = new ListNode(0);
        dump.next = head;
        ListNode cur = dump;
        while (cur != null && cur.next != null) {
            ListNode temp = cur.next;
            if (temp.next != null && temp.val == temp.next.val) {
                ListNode end = temp.next;
                while (temp.next != null && end.val == end.next.val) {
                    end = end.next;
                }
                cur.next = end.next;
            } else {
                cur = cur.next;
            }
        }
        return dump.next;
    }

    //分割两个链表 1-5-4-6-3-2  n =3       1-2-5-4-6-3
    public ListNode divideListNode(ListNode head, int n) {
        ListNode first = new ListNode(0);
        ListNode dump = first;
        ListNode second = new ListNode(0);
        ListNode cur = second;
        while (head != null) {
            if (head.val >= n) {
                cur.next = head;
                cur = cur.next;
                cur.next = null;
            } else {
                dump.next = head;
                dump = dump.next;
                dump.next = null;
            }
            head = head.next;
        }
        cur.next = second.next;
        return first.next;
    }

    //反转链表 m,n 1-2-3-4-5 n=2 m=4  1-4-3-2-5
    //todo 未解决
    public ListNode reverseListNode(ListNode head, int n, int m) {
        if (m <= n) {
            return head;
        }
        ListNode dump = new ListNode(0);
        dump.next = head;
        ListNode cur = dump;
        for (int i = 0; i < n; i++) {
            cur = cur.next;
        }
        head = cur.next;
        for (int i = n; i < m; i++) {
            ListNode nex = head.next;
            head.next = nex.next;//2-4
            nex.next = cur.next;//3-2
            cur.next = nex;//1-2
        }
        return dump.next;
    }

    //有序链表转二叉树
    public TreeNode listToTree(ListNode head) {
        if (head == null) {
            return new TreeNode(0);
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        TreeNode root = new TreeNode(slow.val);
        root.left = listToTree(head);
        root.right = listToTree(slow.next);
        return root;
    }

    //二叉树转链表 https://blog.csdn.net/thousa_ho/article/details/77961918
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            flatten(root.left);
        }
        if (root.right != null) {
            flatten(root.right);
        }
        TreeNode treeNode = root.right;
        root.right = root.left;
        root.left = null;
        while (root.right != null) {
            root = root.right;
        }
        root.right = treeNode;

    }

    //判断链表是否回环
    public boolean isCircleList(ListNode mListNode) {
        ListNode fast = mListNode;
        ListNode slow = mListNode;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    //重排链表 1-2-3-4-5 1-5-2-4-3
    public void orderList(ListNode head) {
        //找到中心点，反转后续链表，向前面链表中插入
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode end = slow.next;
        ListNode dump = end;
        slow.next = null;

        ListNode prev = null;
        //1-2-3-4
        while (dump != null) {
            dump.next = prev;
            prev = dump;
            dump = dump.next;
        }
        ListNode cur = head;
        while (cur != null && prev != null) {
            ListNode nextF = cur.next;
            ListNode nextE = prev.next;
            cur.next = prev;
            prev.next = cur.next;
            cur = nextF;
            prev = nextE;
        }
    }

    //链表插入排序 1-6-2-4    1-2-4-6;
    public ListNode insertList(ListNode head) {
        ListNode dummy = new ListNode(0), pre;
        dummy.next = head;

        while (head != null && head.next != null) {
            if (head.val <= head.next.val) {
                head = head.next;
                continue;
            }
            pre = dummy;

            while (pre.next.val < head.next.val) pre = pre.next;

            ListNode curr = head.next;
            head.next = curr.next;
            curr.next = pre.next;
            pre.next = curr;
        }
        return dummy.next;
    }

    //排序链表,类似归并排序的用法
    public ListNode sortListByCombine(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode end = slow.next;
        slow.next = null;
        ListNode l1 = sortListByCombine(head);
        ListNode l2 = sortListByCombine(end);
        return conbineTreeNode(l1, l2);
    }

    //判断是否为回文链表
    public boolean isCircleList2(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode end = slow.next;
        slow.next = null;
        ListNode pre = null;
        //1-2-3
        while (end != null) {
            end.next = pre;
            end = end.next;
            pre = end;
        }
        while (head != null && pre != null) {
            if (head.val != pre.val) {
                return false;
            }
            head = head.next;
            pre = pre.next;
        }
        return true;
    }

    /**
     * 树系列相关题目
     */

    //判断两个相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p==null&&q==null){
            return true;
        }
        if (p!=null&&q!=null&&p.val==q.val){
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }else {
            return false;
        }
    }
    //判断是否为对称二叉树
    public boolean isMirrorTreeNode(TreeNode l1,TreeNode l2){
        if (l1==null&&l2==null){
            return true;
        }
        if (l1==null||l2==null){
            return false;
        }
        return l1.val==l2.val&&isMirrorTreeNode(l1.left,l2.right)&&isMirrorTreeNode(l1.right,l2.left);
    }
    //二叉树的层次遍历
    public List<List<Integer>> levelOrder(TreeNode head){
        List<List<Integer>> mList = new ArrayList<>();
        Queue<TreeNode> mQueue = new ArrayDeque<>();
        mQueue.add(head);
        while (!mQueue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < mQueue.size(); i++) {
                TreeNode poll = mQueue.poll();
                list.add(poll.val);
                if (poll.left!=null){
                    mQueue.offer(poll.left);
                }
                if (poll.right!=null){
                    mQueue.offer(poll.right);
                }
            }
            mList.add(list);
        }
        return mList;
    }
    //锯齿二叉树遍历
    public List<List<Integer>> zigzagLevelOrder(TreeNode head){
        List<List<Integer>> mList = new ArrayList<>();
        Queue<TreeNode> mQueue = new ArrayDeque<>();
        mQueue.add(head);
        boolean isReverse = true;
        while (!mQueue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < mQueue.size(); i++) {
                TreeNode poll = mQueue.poll();
                list.add(poll.val);
                if (isReverse){
                    if (poll.left!=null){
                        mQueue.offer(poll.left);
                    }
                    if (poll.right!=null){
                        mQueue.offer(poll.right);
                    }
                }else{
                    if (poll.right!=null){
                        mQueue.offer(poll.right);
                    }
                    if (poll.left!=null){
                        mQueue.offer(poll.left);
                    }
                }
            }
            isReverse = !isReverse;
            mList.add(list);
        }
        return mList;
    }
    //获取树的最大深度
    public int maxDepth(TreeNode root){
        return root==null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
    //重建二叉树,通过先序和中序 [3,9,20,15,7] [9,3,15,20,7]
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length==0){
            return null;
        }
        return buildCore(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    private TreeNode buildCore(int[] preorder,int preSt,int preEnd,int[] inorder,int inSt,int inEnd){
        //前序遍历第一个节点是根节点
        int rootValue = preorder[preSt];
        TreeNode root = new TreeNode(rootValue);

        //前序序列只有根节点
        if(preSt == preEnd){
            return root;
        }
        //遍历中序序列，找到根节点的位置
        int rootInorder = inSt;
        while(inorder[rootInorder]!=rootValue&&rootInorder<=inEnd){
            rootInorder++;
        }

        //左子树的长度
        int leftLength = rootInorder - inSt;
        //前序序列中左子树的最后一个节点
        int leftPreEnd = preSt + leftLength;

        //左子树非空
        if(leftLength>0){
            //重建左子树
            root.left = buildCore(preorder,preSt+1,leftPreEnd,inorder,inSt,inEnd);
        }
        //右子树非空
        if(leftLength < preEnd - preSt){
            //重建右子树
            root.right = buildCore(preorder,leftPreEnd +1,preEnd,inorder,rootInorder+1,inEnd);
        }
        return root;
    }
    //有序列表转成二叉树
    public TreeNode sortedArrayToBST(int[] nums) {
        // 左右等分建立左右子树，中间节点作为子树根节点，递归该过程
        return nums == null ? null : buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        }
        int m = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[m]);
        root.left = buildTree(nums, l, m - 1);
        root.right = buildTree(nums, m + 1, r);
        return root;
    }


    class ListNode {
        int val;
        ListNode next;

        public ListNode(int mVal) {
            this.val = mVal;
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}