数据结构和算法的部分例题（力扣）

1.数组

1.1 合并一个数组的两个有序区间

public class MargTwo {
    public static void main(String[] args) {
        int[] arr1={1,5,6,2,4,10,11};
        int[] arr2=new int[arr1.length];
        marg2(arr1,0,2,3,6,arr2);
    }

    private static void marg2(int[]arr1,int iStar,int iEnd,int jStar,int jEnd,int []arr2) {
        int k=0;
        while (iStar<=iEnd&&jStar<jEnd){
            if(arr1[iStar]<arr1[jStar]){
                arr2[k]=arr1[iStar];
                iStar++;
            }else{
                arr2[k]=arr1[jStar];
                jStar++;
            }
            k++;
        }
        if(iStar>iEnd){
            //i区间无元素，复制j区间剩余元素
            System.arraycopy(arr1,jStar,arr2,k,jEnd-jStar+1);
            return;
        }else{
            //复制i区间剩余元素
            System.arraycopy(arr1,iStar,arr2,k,iEnd-iStar+1);
        }
    }



    /**
     * @Description 递归
     * @Author LY
     * @Param [arr1, iStar, iEnd, jStar, jEnd, arr2, k]
     *       arr1： 待合并数组
     *       iStar：第一个区间开始下标
     *       iEnd： 一个区间结束下标
     *       jStar：第二个区间开始下标
     *       jEnd： 二个区间结束下标
     *       arr2： 合并后的数组
     *       k：    新数组下标
     * @return int[]
     * @Date 2024/1/17 16:31
     **/

    private static void marg1(int[]arr1,int iStar,int iEnd,int jStar,int jEnd,int []arr2,int k){
        if(iStar>iEnd){
            //i区间无元素，复制j区间剩余元素
            System.arraycopy(arr1,jStar,arr2,k,jEnd-jStar+1);
            return;
        }else{
            //复制i区间剩余元素
            System.arraycopy(arr1,iStar,arr2,k,iEnd-iStar+1);
        }
        if(arr1[iStar]<arr1[jStar]){
            arr2[k]=arr1[iStar];
            iStar++;
        }else{
            arr2[k]=arr1[jStar];
            jStar++;
        }
        marg1(arr1,iStar,iEnd,jStar,jEnd,arr2,k+1);
    }
}

2.链表?

2.1 反转单向链表

（方法1）构建一个新的链表，从就链表依次拿到每个节点，创建新的节点添加至新链表头部，完成后的新链表就是倒序的，简单，但是需要创建新的对象

//从头部取值插入尾部
    private static ListNode firstToLast(ListNode listNode) {
        //创建新的链表从第一个元素开始向前插入
        ListNode head = null;
        //指针指向传入元素
        ListNode p = listNode;
        while (p != null) {
            //原本的头部变成p.next之后的val元素，
            head = new ListNode(p.val, head);
            p = p.next;
        }
        return head;
    }

（方法2）与方法1类似，构建新的链表，从头部移除节点，添加至新链表头部，完成后新链表既是倒序的，需要构建一个容器类，但是不去创建新的节点，更加偏面向对象

//容器类
    static class MyList {
        ListNode head;

        public MyList(ListNode head) {
            this.head = head;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if (first != null) {
                head = first.next;
            }
            return first;
        }

        public void addFirst(ListNode first) {
            first.next = head;
            head = first;
        }

    }


    //从头部移除元素插入新链表尾部
    private static MyList moveFirst(ListNode listNode) {
        MyList oMyList = new MyList(listNode);
        MyList nMyList = new MyList(null);
        while (oMyList.head != null) {
            nMyList.addFirst(oMyList.removeFirst());
        }
        return nMyList;
    }

（方法3）利用递归特性，让最后一个节点指向他的上一个节点，上一个节点指向null

  //递归调用，最后一个节点
    private static ListNode adjoin(ListNode listNode) {
        //链表为空或者下一个节点为空直接返回
        if (listNode == null || listNode.next == null) {
            return listNode;
        }
        //否则向下寻找
        ListNode last = adjoin(listNode.next);
        //让当前节点的下一个节点的下一个节点指向当前节点
        listNode.next.next = listNode;
        //当前节点下一个节点指向空
        listNode.next = null;
        return last;
    }

（方法4）每次都取第二个节点插入到头部，直到第二个节点为null，但是要考虑链表只有一个元素或者为null的特殊情况

/*
     * 设置两个指针，old1，old2和new old1，new1都指向第一个节点，old2指向就链表的第二个元素
     * 不断地将old2插入到new的前方，old.next==null结束调用
     * */
    private static ListNode oldToNew(ListNode old1) {
        //处理空链表和一个元素
        if(old1==null||old1.next==null){
            return old1;
        }
        //第二个节点
        ListNode old2 = old1.next;
        //新的链表
        ListNode new1 = old1;
        //old为空终止循环
        while (old2 != null) {
            //断开old2
            old1.next = old2.next;
            //把old2.next指向new1
            old2.next = new1;
            //new1重新赋值
            new1=old2;
            //old2指向下一个节点
            old2=old1.next;
        }
        return new1;
    }

（方法5）类似于方法2，但是不用创建新的容器，偏向于面向过程

/*
    *  类似于firstToLast，不用MyList
    * */
    private static ListNode firstToLast2(ListNode old1) {
        //处理空链表和一个元素
        if(old1==null||old1.next==null){
            return old1;
        }
        //新链表
        ListNode new1=null;
        while (old1!=null){
            ListNode old2=old1.next;
            old1.next=new1;
            //old1为需要的节点
            new1=old1;
            //old2为断开第二个节点后的链表
            old1=old2;
        }
        return new1;
    }

2.2?根据值删除节点

public class DeleteByVal {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1, new ListNode(2, new ListNode(3, null)));
        ListNode listNode2 = new ListNode(1, new ListNode(2, new ListNode(2, null)));
        ListNode listNode3 = new ListNode(2, new ListNode(2, new ListNode(2, null)));
        ListNode remove1 = remove(listNode1, 2);
        ListNode remove2 = remove(listNode2, 2);
        ListNode remove3 = remove(listNode3, 2);

        ListNode remove4 = remove2(listNode1, 2);
        ListNode remove5 = remove2(listNode2, 2);
        ListNode remove6 = remove2(listNode3, 2);
    }

    public static ListNode remove2(ListNode p, int val) {
        if (p == null) {
            return null;
        }
        if (p.val == val) {
            return remove2(p.next, val);
        }else{
            p.next= remove2(p.next, val);
        return p;
        }
    }

    public static ListNode remove(ListNode head, int val) {
        //创建哨兵
        ListNode s = new ListNode(-1, head);
        ListNode piont1 = s;
        ListNode piont2 = s.next;
        while (piont2 != null) {
            if (val == piont2.val) {
                //删除只移动p2
                piont1.next = piont2.next;
                piont2 = piont1.next;
            } else {
                //不删除移动p1，p2
                piont1 = piont2;
                piont2 = piont2.next;
            }
        }
        return s.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

2.3 删除倒数节点

public class DeleteTailend {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
//        listNode=remove(listNode, 5);
        listNode=remove2(listNode, 5);
    }
    //快慢指针法
    public static ListNode remove2(ListNode listNode, int n) {
        ListNode s=new ListNode(-1,listNode);
        ListNode p1=s;
        ListNode p2=s;
        for (int i = 0; i < n+1; i++) {
            p2=p2.next;
        }
        while(p2!=null){
            p1=p1.next;
            p2=p2.next;
        }
        p1.next=p1.next.next;
        return s.next ;
    }
    //删除倒数第n个接点 递归
    public static ListNode remove(ListNode listNode, int n) {
        ListNode s=new ListNode(-1,listNode);
        recurs( s, n);
        return s.next ;
    }
    private static int recurs(ListNode p,int n){
        if (p == null) {
            return 0;
        }
       int nth= recurs(p.next, n);
        if(nth==n){
            p.next=p.next.next;
        }
        return nth+1;
    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

2.4 有序链表重复节点（保留1个）

public class DeleteRepetition {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(3, new ListNode(3, new ListNode(3, new ListNode(3, null)))));
        ListNode remove = remove2(listNode);
    }

    public static ListNode remove2(ListNode listNode){
        if(listNode==null|| listNode.next==null){
            return listNode;
        }
        if(listNode.val==listNode.next.val){
            //重复 则不要当前节点
            return remove2(listNode.next);
        }else{
            //下一个节点要更新为.next去重后的链表
            listNode.next=remove2(listNode.next);
            return listNode;
        }
    }

    public static ListNode remove(ListNode listNode){
        if(listNode==null|| listNode.next==null){
            return listNode;
        }
        ListNode p1=listNode;
        ListNode p2=listNode.next;
        while (p2!=null){
            if(p1.val==p2.val){
                p1.next=p2.next;
            }else{
                p1=p2;
            }
            p2=p1.next;
        }
        return listNode;
    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

2.5?有序链表重复节点（全部删除）

public class DeleteRepetition2 {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(3, new ListNode(3, null)))));
        ListNode remove = remove2(listNode);
    }
    //快慢指针
    public static ListNode remove2(ListNode listNode){
        if(listNode==null|| listNode.next==null){
            return listNode;
        }
        ListNode s=new ListNode(-1,listNode);
        ListNode pinot1=s;
        ListNode pinot2,pinot3;
        while ((pinot2=pinot1.next)!=null&& (pinot3=pinot2.next)!=null){
            if(pinot3!=null&&pinot2.val==pinot3.val){
                while ((pinot3=pinot3.next)!=null&&pinot3.val==pinot2.val){
                }
                pinot1.next=pinot3;
            }else{
                pinot1=pinot1.next;
            }
        }
        return listNode;
    }
    public static ListNode remove(ListNode listNode){
        if(listNode==null|| listNode.next==null){
            return listNode;
        }
        //前后值一样
        if(listNode.val==listNode.next.val){
            //去寻找下一个直到与当前节点不同
            ListNode x=listNode.next.next;
            while (x!=null && x.val==listNode.next.val){
                //返回他的下一个节点
                x=x.next;
            }
            return remove(x);
        }else {
            //更新next后的节点也需要去重
            listNode.next=remove(listNode.next);
            return listNode;
        }
    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

2.6 合并有序链表

public class MergeTwo {

    public static void main(String[] args) {
      /*  ListNode listNode1 = new ListNode(1, new ListNode(2, new ListNode(2, null)));
        ListNode listNode2 = new ListNode(3, new ListNode(3, new ListNode(4, null)));
        ListNode marge = marge(listNode1, listNode2);
        ListNode listNode3 = new ListNode(1, new ListNode(3, new ListNode(5, null)));
        ListNode listNode4 = new ListNode(2, new ListNode(4, new ListNode(6, null)));
        ListNode marge2 = marge(listNode1, listNode2);*/
       /* ListNode listNode1 = new ListNode(1, new ListNode(2, new ListNode(2, null)));
        ListNode listNode2 = new ListNode(3, new ListNode(3, new ListNode(4, null)));
        ListNode marge = marge2(listNode1, listNode2);*/
        ListNode listNode3 = new ListNode(1, new ListNode(3, new ListNode(5, null)));
        ListNode listNode4 = new ListNode(2, new ListNode(4, new ListNode(6, null)));
        ListNode marge2 = marge2(listNode3, listNode4);
    }

    //递归
    public static ListNode marge2(ListNode listNode1, ListNode listNode2) {
        if (listNode1 == null) {
            return listNode2;
        }
        if (listNode2 == null) {
            return listNode1;
        }
        if (listNode1.val < listNode2.val) {
            listNode1.next = marge2(listNode1.next, listNode2);
            return listNode1;
        } else {
            listNode2.next = marge2(listNode1, listNode2.next);
            return listNode2;
        }
    }

    //循环处理
    public static ListNode marge(ListNode listNode1, ListNode listNode2) {
        ListNode s = new ListNode(-1, null);
        ListNode p = s;
        while (listNode1 != null && listNode2 != null) {
            //把小的值插入到链表后方
            if (listNode1.val > listNode2.val) {
                //listNode2小，插入listNode2的值到新的链表，并将指针后移
                p.next = listNode2;
                listNode2 = listNode2.next;
            } else if (listNode1.val < listNode2.val) {
                //listNode1小，插入listNode1的值到新的链表，并将指针后移
                p.next = listNode1;
                listNode1 = listNode1.next;
            } else {
                p.next = listNode1;
                listNode1 = listNode1.next;
                p = p.next;
                p.next = listNode2;
                listNode2 = listNode2.next;
            }
            //将新链表指针移动到最后
            p = p.next;
        }
        //生效的全部都是大的
        if (listNode1 != null) {
            p.next = listNode1;
        }
        if (listNode2 != null) {
            p.next = listNode2;
        }
        return s.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

2.7 合并多个有序链表

public class MergeMany {

    public static void main(String[] args) {

        ListNode listNode1 = new ListNode(1, new ListNode(4, new ListNode(7, null)));
        ListNode listNode2 = new ListNode(1, new ListNode(5, new ListNode(8, null)));
        ListNode listNode3 = new ListNode(3, new ListNode(6, new ListNode(9, null)));
        ListNode []list ={listNode1,listNode2, listNode3};
        ListNode spilt = spilt(list, 0, list.length - 1);
    }

    /**
     * @Description 返回合并后的数组
     * @Author LY
     * @Param [list, i, j]  list 数组 ， i左边界，j右边界
     * @Date 2024/1/17 10:05
     **/

    private static ListNode spilt(ListNode[] list,int i,int j){
        //结束条件 数组内只有一个链表
        if(i==j){
            return  list[i];
        }
        int m = i+j >>>1;//取中间
        //从0到中间
        ListNode left = spilt(list, 0, m);
        //从中间+1到结束
        ListNode right = spilt(list, m + 1, j);
        return marge(left,right);
    }

    //循环处理合并两个链表
    public static ListNode marge(ListNode listNode1, ListNode listNode2) {
        ListNode s = new ListNode(-1, null);
        ListNode p = s;
        while (listNode1 != null && listNode2 != null) {
            //把小的值插入到链表后方
            if (listNode1.val > listNode2.val) {
                //listNode2小，插入listNode2的值到新的链表，并将指针后移
                p.next = listNode2;
                listNode2 = listNode2.next;
            } else if (listNode1.val < listNode2.val) {
                //listNode1小，插入listNode1的值到新的链表，并将指针后移
                p.next = listNode1;
                listNode1 = listNode1.next;
            } else {
                p.next = listNode1;
                listNode1 = listNode1.next;
                p = p.next;
                p.next = listNode2;
                listNode2 = listNode2.next;
            }
            //将新链表指针移动到最后
            p = p.next;
        }
        //生效的全部都是大的
        if (listNode1 != null) {
            p.next = listNode1;
        }
        if (listNode2 != null) {
            p.next = listNode2;
        }
        return s.next;
    }
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

2.8 查找中间节点

public class FindMiddle {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, new ListNode(7, null)))))));
        ListNode listNode2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, null))))));
        ListNode middle1 = findMiddle1(listNode1);
        ListNode middle2 = findMiddle1(listNode2);
    }

    /*
     * 快慢指针
     * 快指针一次走两个，慢指针一次走一个，
     * 当快指针走到结束，慢指针则在链表中间元素
     *
     *
     * */
    private static ListNode findMiddle1(ListNode head){
        ListNode quick=head;
        ListNode slow=head;
        while (slow!=null&&slow.next!=null){
            slow =slow.next;
            quick=quick.next.next;
        }
        return slow;

    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

2.9 判断回文链表

public class IsPalindrome {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(3, new ListNode(2, new ListNode(1,null))))));
        ListNode listNode2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(2, new ListNode(1,null)))));
        ListNode listNode3 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(3, new ListNode(1,null)))));
        Boolean palindrome1 = isPalindrome(listNode1);
        Boolean palindrome2 = isPalindrome(listNode2);
        Boolean palindrome3 = isPalindrome(listNode3);
    }

    /*
    *   优化，合并代码
    *
    * */
    public static Boolean isPalindrome(ListNode head){
        /*//查找中间元素
        ListNode quick=head;
        ListNode slow=head;
        while (quick!=null&&quick.next!=null){
            slow =slow.next;
            quick=quick.next.next;
        }
        //反转链表
        ListNode n1=null;
        while (slow!=null){
            //旧节点的下一个
            ListNode old2=slow.next;
            //旧链表第一个节点和新链表链接
            slow.next=n1;
            //新链表为旧链表和新链表链接后的结果
            n1=slow;
            //旧链表等于他的下一个元素
            slow=old2;
        }*/
        //查找和反转合并
        ListNode quick=head;//快指针
        ListNode slow=head;//慢指针
        ListNode old1=head;//旧的头部
        ListNode new1=null;//新的头部
        while (quick!=null&&quick.next!=null){
            slow =slow.next;
            quick=quick.next.next;
            //反转逻辑
            //旧节点的下一个
            ListNode  old2=old1.next;
            old1.next=new1;
            new1=old1;
            old1=old2;
        }
        while (new1.next!=null){
            if(quick!=null){
                //奇数节点
                slow=slow.next;
            }
            if(new1.val!=slow.val){
                return false;
            }
            new1=new1.next;
            slow=slow.next;
        }
        return true;

    }

    /*
    * 1.查找到中间节点，
    * 2.向后的元素全部反转，
    * 3.然后从头开始判断，完全相同则为回文链表
    * */

    public static Boolean isPalindrome2(ListNode head){
        //查找中间元素
        ListNode middle1 = findMiddle1(head);
        //反转链表
        ListNode reverse = reverse(middle1);
        while (reverse.next!=null){
            if(reverse.val!=head.val){
                return false;
            }
            reverse=reverse.next;
            head=head.next;
        }
        return true;

    }
    private static ListNode reverse(ListNode old1){
        ListNode n1=null;
        while (old1!=null){
            //旧节点的下一个
            ListNode old2=old1.next;
            //旧链表第一个节点和新链表链接
            old1.next=n1;
            //新链表为旧链表和新链表链接后的结果
            n1=old1;
            //旧链表等于他的下一个元素
            old1=old2;
        }
        return n1;
    }

    /*
     * 快慢指针
     * 快指针一次走两个，慢指针一次走一个，
     * 当快指针走到结束，慢指针则在链表中间元素
     *
     *
     * */
    private static ListNode findMiddle1(ListNode head){
        ListNode quick=head;
        ListNode slow=head;
        while (quick!=null&&quick.next!=null){
            slow =slow.next;
            quick=quick.next.next;
        }
        return slow;

    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

2.10 判环算法

? ? ?

? ? ? ? 判环算法通常是指用于检测在链表或数组等数据结构中是否存在环的一种方法。这里以链表中的判环算法为例，其中最经典的实现是Floyd判环算法（也称作龟兔赛跑算法）。

Floyd判环算法详解：

1. 基本思想：

   • 假设有两个指针，一个快指针（比如兔子）每次移动两个节点，另一个慢指针（比如乌龟）每次移动一个节点。
   • 如果链表中不存在环，因为快指针速度更快，它最终会到达链表的尾部而结束遍历，此时可以确定无环。
   • 若链表中存在环，则快指针会在某个时刻追上慢指针，因为在环内它们一直在循环，并且由于速度差的关系，必然会在环内的某一点相遇。

2. 算法步骤：

   • 初始化两个指针fast和slow，都指向链表头结点。
   • 当fast和slow都不为空时，持续进行以下操作：
     • fast指针向前移动两个节点（fast = fast.next.next）。
     • slow指针向前移动一个节点（slow = slow.next）。
   • 检查fast和slow是否指向同一个节点。如果是，则说明链表中有环；否则，若fast达到链表末尾（即fast.next == null），则说明链表无环。

3. 计算环长度（可选）：

   • 在判断出有环之后，为了找到环的长度，可以让其中一个指针（如slow）保持不动，另一个指针（fast）重置到头结点并每次只前进一个节点。
   • 这样当fast再次与slow相遇时，fast所走过的步数除以2就是环的长度（因为之前相遇时，fast走了slow两倍的距离）。

4. 时间复杂度和空间复杂度：

   • 时间复杂度：O(n)，其中n为链表的长度。最坏情况下，两个指针都需要遍历整个链表一次才能确定是否有环。
   • 空间复杂度：O(1)，因为只需要常数级别的额外空间来存储两个指针。

? ? ? ?通过这种巧妙的方法，Floyd判环算法可以在不增加额外空间复杂度的情况下高效地检测链表中是否存在环。

? ? ? ?假设乌龟和兔子相遇在环中的某一点P，由于兔子每次移动两个节点，而乌龟每次移动一个节点，在它们相遇时，兔子相对于乌龟多走了一倍的距离。这一倍的距离实际上就是从头结点开始到环入口点的链长，因为在这段距离里，兔子比乌龟每轮循环都多前进一个节点，所以最终能在环内相遇。

? ? ? ?首先，兔子和乌龟从同一个起点开始，兔子每次移动两个节点，乌龟每次移动一个节点。当它们在环内相遇时，假设兔子走了m步（经过了m个节点），乌龟走了n步（经过了n个节点），且m = 2n（因为兔子速度是乌龟的两倍）。

此时，兔子相对于乌龟多走了一倍的距离，这一倍的距离实际上是从链表头部到环入口点的距离，记作d。

? ? ? ?接下来为了计算环的大小（即环中的节点数），我们可以让乌龟保持不动，而将兔子重置回头结点，然后两者都以乌龟的速度（一次一格）前进。再次相遇时，兔子又走过了d距离加上环的一个完整周长c。

所以有：兔子第二次走过的总距离 = d + c。

? ? ? ?由于兔子第二次走的速度与乌龟相同，乌龟也同步前进了c距离（环的周长）。因此：

兔子走的距离 - 乌龟走的距离 = (d + c) - c = d

? ? ? ?这里d就是从链表头到环入口的距离。

在Floyd判环算法中，d是从链表头到环入口的距离的原因可以这样解释：

1. 初始时，兔子（快指针）和乌龟（慢指针）都从链表的头结点开始移动。

2. 兔子每次移动两个节点，乌龟每次移动一个节点。当链表存在环时，因为兔子的速度是乌龟的两倍，在环内兔子最终会追上乌龟，即两者在环中的某一点相遇。

3. 从开始至相遇过程中，兔子走过的路径包含了从链表头到环入口的这段距离d（因为兔子先到达了环），以及环内的一部分或几圈。而乌龟走过的路径只包含了从链表头到环入口的这段距离d以及与乌龟相遇位置相对应的环内部分。

4. 当兔子追上乌龟时，由于兔子的速度更快，它在环内的多走的部分刚好等于乌龟还未进入环前的那段距离d。也就是说，兔子比乌龟多走了一个从头结点到环入口的距离。

因此，我们说d是从链表头到环入口的距离。如果要计算环的大小，可以通过让其中一个指针停留在相遇点，另一个指针重置回头结点，然后两个指针以相同速度前进再次相遇的方式来实现，此时两者共同走过的额外距离就是环的长度。

public class IsAnnulus {
    public static void main(String[] args) {
        ListNode listNode=new ListNode(-1,null);
        ListNode listNode1 = new ListNode(1,null);
        ListNode listNode2 = new ListNode(2,null);
        ListNode listNode3 = new ListNode(3,null);
        ListNode listNode4 = new ListNode(4,null);
        ListNode listNode5 = new ListNode(5,null);
        ListNode listNode6 = new ListNode(6,null);
        listNode.next=listNode4;
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode;
        ListNode aunnulus1 = isAunnulus(listNode1);
        listNode4.next=listNode5;
        listNode5.next=listNode6;
        listNode6.next=listNode;
        //第一次相遇
        ListNode aunnulus2 = isAunnulus(listNode1);
        //第二次相遇，环的入口
        ListNode aunnulus3 = findEntrance(listNode1);
    }

    //确认是否有环
    private static ListNode findEntrance(ListNode head){
        ListNode quick=head;
        ListNode slow=head;
        if(head==null){
            return null;
        }
        while (quick!=null&&quick.next!=null){
            slow=slow.next;
            quick=quick.next.next;
            if(slow==quick){
                slow=head;
                while (true){
                    //如果quick等于head，说明首尾首相连
                    if(slow==quick){
                        return slow;
                    }
                    slow=slow.next;
                    quick=quick.next;
                    if(quick==slow){
                        return slow;
                    }
                }
            }
        }
        return null;
    }

    //确认是否有环
    private static ListNode isAunnulus(ListNode head){
        ListNode quick=head;
        ListNode slow=head;
        if(head==null){
            return null;
        }
        while (quick!=null&&quick.next!=null){
            slow=slow.next;
            quick=quick.next.next;
            if(slow==quick){
               return slow;
            }
        }
        return null;
    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

3.递归(补充)

递归定义：

????????递归通常用于解决问题的一种方法，其中一个问题的解决方案可以通过解决其更小的同类问题来构建。这里的“同一类概念的更小子集”是指将原问题分解为一个或多个与原问题相似但规模更小的子问题

? ? ? ? （1）自己调用自己（有规律的）。

? ? ? ? （2）每次调用，函数处理的数据规模，会较上次缩减（子集），而后许逐步缩减到无需递归。

? ? ? ? （3）内层函数调用（子集处理）完成，外层函数才能算调用完成。

  //调用递归
    public void recursionLoop(){
        this.recursion(sentinel.next);
    }
    //递归遍历
    private void recursion(Node curr){
        if(curr !=sentinel){
            System.out.println("befor"+curr.value);
            recursion(curr.next);
            System.out.println("after"+curr.value);

        }
    }
//befor1,befor4,befor5,befor6,befor7
//after7,after6,after5,after4,after1

思路：

? ? ? ? 能否使用递归求解。

? ? ? ? 推导出地推关系：父问题与子问题之间的关系，以及递归结束的条件。

例如之前遍历的链表递推关系为：

f(n)	停止	curr==sentinel
	f(n.next)	curr!=sentinel

深入到最里层叫做：递。

从最里层出来叫做：归。

在递的过程中，外层函数内的局部变量（及方法参数并未消失），归的时候还可以用到。

?3.1 N的阶乘

递推关系：

f(n)	停止	n==1
	n*f(n-1)	n>1

  public static void main(String[] args) {
        System.out.println(factorialN(10));

    }
    public static int factorialN(int n){
        if(n==1){
            return 1;
        }
        return n*factorialN(n-1);
    }

3.2 反向打印字符串

递推关系：

f(n)	停止	n==str.length
	f(n+1)	0<=n<=str.length

public static void main(String[] args) {
        reverseStr(0,"abcdefg");
    }
    //反向打印字符串
    public static void reverseStr(int n,String str){
        if(n==str.length()){
            return;
        }
        reverseStr(n+1,str);
        System.out.println(str.charAt(n));
    }

?3.3递归二分查找

 public static void main(String[] args) {
        int [] arr={1,2,3,4,5,6,7,8,9,10};
        System.out.println( recursionBinarySearch(arr,5));
        System.out.println( recursionBinarySearch(arr,1));
        System.out.println( recursionBinarySearch(arr,10));
        System.out.println( recursionBinarySearch(arr,11));
    }
    public static int recursionBinarySearch(int []arr,int target){
        return recursionBinarySearch(arr,0,arr.length-1,target);
    }
    //递归二分查找
    private static int  recursionBinarySearch(int []arr,int i,int j,int target){
        if(i>j)  {return -1;}
        int m =(i+j)>>>1;
        if(target<arr[m]){
           return recursionBinarySearch(arr,i,m-1,target);
        }else if(arr[m]<target){
            return  recursionBinarySearch(arr,m+1,j,target);
        }else {
            return m;
        }
    }

3.4 递归冒泡排序

递推关系：

f(n)	停止	j==0
	f(j-1)	arr.length-1>j>0

 public static void main(String[] args) {
        System.out.print("排序前==》");
        int[] randomArr = getRandomArr();
        bubbleSort(randomArr);
        System.out.println();
        System.out.print("排序后==》");
        for (int num : randomArr) {
            System.out.print(num + "，");
        }
    }

    //递归实现冒泡排序
    public static void bubbleSort(int [] arr){
        bubbleSort( arr,arr.length-1);
    }
    /**
     * @Description
     * @Author LY
     * @Param [arr, j] arr:需要排序数组，j需要排序的右边界
     * @return void
     * @Date 2023/12/18 15:29
     **/

    private static void bubbleSort(int arr[],int j){
        if(j==0){
            return;
        }
        for (int i = 0; i < j; i++) {
            if(arr[i]>arr[i+1]){
              int temp=  arr[i];
              arr[i]=arr[i+1];
              arr[i+1]=temp;
            }
        }
        bubbleSort(arr,j-1);
    }
    //获取一个随机数组
    public static  int[] getRandomArr(){
        int n = 10; // 随机数组的长度
        int lowerBound = 0; // 数组元素的最小值
        int upperBound = 50; // 数组元素的最大值

        Random random = new Random();
        int[] randomArray = new int[n];
        for (int i = 0; i < n; i++) {
            randomArray[i] = random.nextInt(upperBound - lowerBound + 1) + lowerBound;
        }
        for (int num : randomArray) {
            System.out.print(num + "，");
        }
        return randomArray;
    }

3.4 递归冒泡排序-改进

有些排序后，已经是有序地元素排列，下次比较无需重新对比，如果使用j，每次递减1，会导致效率下降，可以定义一个x，当i发生交换，x=1；不发生交换说明后续元素都是顺序排列了。

 private static void bubbleSort2(int arr[],int j){
        if(j==0){
            return;
        }
        int x=0;
        for (int i = 0; i < j; i++) {
            if(arr[i]>arr[i+1]){
                int temp=  arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
                x=i;
            }
        }
        bubbleSort2(arr,x);
    }

3.5插入排序

递推关系：

f(n)	停止	n==arr.length
	f(arr,low)	0<n<arr.length

public static void main(String[] args) {
        System.out.print("排序前==》");
        int[] randomArr = getRandomArr();
        insertionSort(randomArr);
        System.out.println();
        System.out.print("排序后==》");
        for (int num : randomArr) {
            System.out.print(num + "，");
        }
    }
    //递归实现插入排序
    public static void insertionSort(int [] arr){
        insertionSort(arr,1);
    }
    /**
     * @Description
     * @Author LY
     * @Param [arr, low] arr：需要排序的数组，low 未排序区域的左边界
     * @return void
     * @Date 2023/12/20 13:50
     **/

    public static void insertionSort(int [] arr,int low){
        if(low==arr.length){
            return;
        }
        //存储low指针指向元素
        int temp=arr[low];
        int i=low-1;//i是已排序区域的右边界
        while (i>=0&&arr[i]>temp){
            arr[i+1]=arr[i];//空出插入位置
            i--;//继续向左
        }
        //找到插入位置
        if(i+1!=low){
        arr[i+1]=temp;}
        insertionSort(arr,low+1);
    }

插入排序是将插入元素与前一个元素逐个比较，直到找到arr[i-1]<temp<arr[i]，temp为要插入的位置，如果不满足，则逐个后移。

3.6 多路递归-斐波那契

之前的例子，每个递归函数只包含一个自身的调用，这称之为：single recursion。

如果每个递归函数包含多个自身调用则称之为：multi?recursion。

递推关系：

f(n)	0	n=0
	1	n=1
	f(n-1)+f(n-2)	n>1

public static void main(String[] args) {
        int fibonacci = fibonacci(8);
        System.out.println("斐波那契数列求和："+fibonacci);
    }
    public static int  fibonacci(int n){
        if(n<=1){
            return n;
        }else {
            return fibonacci(n - 1)+fibonacci(n - 2);
        }
    }
    //获取1-100随机正整数
    public static int getRandom(){
        Random rand = new Random();
        int randomNum = rand.nextInt(100) + 1;
        System.out.print("取得随机数："+randomNum);
        return randomNum;
    }

（1）递归次数也符合斐波那契规律：2*f*(n+1)-1。

（2）时间复杂度推导过程：

? ? ? ??

3.6.1 斐波那契-兔子问题

第一个月有一对未成熟的兔子，第二个月他们成熟，第三个月他们能产下一对新的小兔子，求第n个月的兔子数。

    public static int fibonacciRabbit(int n){
        if(n<=2){
            return 1;
        }
        return fibonacciRabbit(n-1)+fibonacciRabbit(n-2);
    }

?3.6.2 斐波那契-青蛙问题

青蛙一次可以跳一个台阶，或者两个台阶，跳n阶一共有几种跳法。

?    public static int fibonaccifrog(int n) {
        if(n<=2){
            return n;
        }
       return fibonaccifrog(n-1)+fibonaccifrog(n-2);
    }

?

?3.6.3斐波那契-优化-缓存

????????fibonacci方法是一个未优化的递归实现，每次计算斐波那契数时都会递归调用自身两次，这导致了大量的重复计算。其时间复杂度为O(2^n)。
????????fibonacciOptimize方法是一个优化过的版本，它使用了动态规划的思想，通过一个缓存数组cache来存储已经计算过的斐波那契数。在计算某个斐波那契数时，首先检查它是否已经在缓存中，如果在，则直接返回缓存的值；如果不在，则计算后将结果存入缓存，然后再返回。这样就避免了重复计算，大大提高了效率。其时间复杂度为O(n)。

随着数据规模的增加，两者运行时间差异就会越来越大。

  public static void main(String[] args) {
        int n=3;
        long OptimizeTime=0;
        long fibonacciTime=0;

        int ite=10;
        for (int i = 0; i < ite; i++) {
            long fibonacciStarOptimize = System.currentTimeMillis();
            int fibonacciOptimize = fibonacciOptimize(n);
            System.out.println("fibonacciOptimize:第"+i+"次结果："+fibonacciOptimize);
            long fibonacciEndOptimize = System.currentTimeMillis();
            OptimizeTime+=(fibonacciEndOptimize-fibonacciStarOptimize);
        }
        for (int i = 0; i < ite; i++) {
            long fibonacciStar = System.currentTimeMillis();
            int fibonacci = fibonacci(n);
            System.out.println("fibonacci:第"+i+"次结果："+fibonacci);
            long fibonacciEnd = System.currentTimeMillis();
            fibonacciTime+=(fibonacciEnd-fibonacciStar);
        }
        System.out.println("OptimizeTime平均执行时间为："+(OptimizeTime/ite));

        System.out.println("fibonacci平均执行时间为："+(fibonacciTime/ite));

    }
    public static int  fibonacciOptimize(int n) {
        int[] cache=new int[n+1];
        //初始化数组内容为-1
        Arrays.fill(cache,-1);
        //初始化第一个和第二个元素
        cache[0]=0;
        cache[1]=1;
        return fibonacci2(n,cache);
    }
        //斐波那契数列优化
    public static int  fibonacci2(int n,int[]cache){
        if(cache[n]==-1){
            cache[n]= fibonacci2(n - 1,cache)+fibonacci2(n - 2,cache);
        }
        return cache[n];
    }
    //斐波那契数列
    public static int  fibonacci(int n){
        if(n<=1){
            return n;
        }else {
            return fibonacci(n - 1)+fibonacci(n - 2);
        }
    }

?3.7 递归-爆栈问题

????????爆栈问题通常发生在编程中使用递归调用时，特别是在没有适当优化或者处理深度较大的递归情况下。当递归调用的层次过深，超过了系统为函数调用分配的栈空间（Stack）的大小限制时，就会发生栈溢出（Stack Overflow），也就是所谓的“爆栈”。

????????在未优化的斐波那契数列计算中，如原始的fibonacci方法，每次递归都会产生两个新的递归调用，导致调用栈的增长非常快。对于较大的n值，这将迅速耗尽栈空间，从而导致爆栈。

解决方案：

为了避免爆栈问题，可以采取以下几种方法：

????????使用迭代代替递归：将递归算法转换为循环迭代算法，这样就可以避免栈空间的持续增长。
????????使用尾递归优化：某些编程语言和编译器支持尾递归优化。在尾递归优化中，如果递归调用是函数体中的最后一句，并且返回值直接是该递归调用的结果，编译器或解释器可以避免创建新的栈帧，从而减少栈空间的使用。然而，Java目前并不原生支持尾递归优化。
????????使用记忆化技术（如在这个例子中的fibonacciOptimize方法）：通过存储已经计算过的中间结果，避免重复计算，从而减少递归调用的深度和次数。
????????增大栈空间大小：虽然这不是一个根本的解决办法，但在某些情况下，可以通过设置程序或环境变量来增大栈空间的大小，以防止爆栈。但这只是临时解决方案，对于非常大的输入值，最终仍然可能遇到栈溢出问题。

3.7.1 尾调用

? ? ? ? 如果一个函数的最后一个是调用一个函数那么可以称之为尾调用，一些编译器会自动优化尾调用：

function a(){
    return b()
}

以下下三段代码不能算作尾调用：

（1）最后一步并非调用函数

function a(){
    const c=b();
    return c;
}

（2）最后一步虽然调用了函数，但是调用结束又用到了外层函数的值1

function a(){
    return b()+1;
}

（3）最后一步虽然调用了函数，但是调用结束又用到了外层函数的值x

function a(x){
    return b()+x;
}

会优化的部分语言：

（1）JavaScript (ES6 及以上)：在严格模式下，JavaScript 引擎实现了尾调用优化。这使得在满足特定条件的尾递归调用中，引擎可以避免创建新的栈帧，从而防止栈溢出。
（3）Lua：Lua 语言支持尾调用优化，它能够识别并优化尾递归调用，以减少栈空间的使用。
（4）Scheme 和 Racket：作为 Lisp 家族的一员，Scheme 和 Racket 语言强制要求实现尾调用优化，这是它们语言规范的一部分。
（5）Haskell：虽然 Haskell 不是通过传统的函数调用栈来处理函数调用，但它的惰性求值和无环数据类型结构在某种程度上提供了类似于尾调用优化的效果。
（6）Erlang：Erlang 语言对尾调用进行了优化，因为其设计目标之一就是支持高并发和容错的系统，其中尾调用优化对于避免栈溢出至

关重要。
（7）OCaml 和 F#：这些函数式编程语言也支持尾调用优化。

?3.7.2 尾递归

尾递归是一种特殊的尾调用。优化之后，当他调用内层函数时，会释放外层函数内存。

3.7.3 循环解决

解决递归爆栈问题，根本的解决方案是不适用递归，所有递归都可以改成循环（有些递归修改为循环比较困难）：

public static void main(String[] args) {
        long sum = 0;
//        sum=sum(10500);
        for (int i = 0; i < 50000; i++) {
            sum+=i;
        }
        System.out.println("求和值："+sum);
    }

3.8计算递归时间复杂度-定理求解

3.8.1 例题

?3.8.2 二分查找-递归版

?3.8.3 归并排序-递归版

3.8.4 快速排序-分好

3.9计算递归时间复杂度-展开求解

3.9.1 递归求和

3.9.2 递归冒泡排序

3.9.3 快排-未分好

3.9.4 汉诺塔

public class RecursionProblemMain {
    public static void main(String[] args) {
        initTowerOfHanoi(3);
        move(3,a,b,c);
    }

    static LinkedList<Integer> a=new LinkedList<>();
    static LinkedList<Integer> b=new LinkedList<>();
    static LinkedList<Integer> c=new LinkedList<>();
    //汉诺塔
    public static void towerOfHanoi(int n){
        initTowerOfHanoi( n);
        print();
        b.addLast(a.removeLast());
        print();

    }
    /**
     * @Description
     * @Author LY
     * @Param [n, a, b, c]n：圆盘个数，a：原本位置，b：借助位置，c：目标位置
     * @return void
     * @Date 2023/12/22 16:04
     **/

    static void move(int n,LinkedList<Integer>a,LinkedList<Integer>b,LinkedList<Integer>c){
        if(n==0){
            return;
        }
        move(n-1,a,c,b);
        //最后一个盘子从a移动到c
        c.addLast(a.removeLast());
        print();
        move(n-1,b,a,c);
    }
    static void print(){
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
        System.out.println("-------------");
    }
    static void initTowerOfHanoi(int n){
        for (int i = n; i >0; i--) {
            a.addLast(i);
        }
    }

    //递归求和
    public static long sum(long n) {
        if (n == 1) {
            return 1;
        }
        return sum(n - 1) + n;
    }


}

3.9.5 杨辉三角

public class Triangle {
    public static void main(String[] args) {
        //Triangle1.print(6);
//        Triangle2.print(6);
        Triangle3.print(6);
    }
    //一维数组优化 优化二维数组的空间
    static class Triangle3 {
        //数组每一列的每个位置的元素都等于上一行row[j]+row[j-1]
        private static void createRow(int [] row,int i){
            if(i==0){
                row[0]=1;
                return;
            }
            for (int j = i; j >0; j--) {
                row[j]=row[j]+row[j-1];
            }
        }

        private static void printSpacing(int n, int i) {
            int num = (n - 1 - i) * 2;
            for (int j = 0; j < num; j++) {
                System.out.print(" ");
            }
        }
        //打印创建好的数组的相应位置的元素
        private static void print(int n) {
            int []  row=new int[n];
            for (int i = 0; i < n; i++) {
                createRow(row,i);
                printSpacing(n, i);
                for (int j = 0; j <= i; j++) {
                    System.out.printf("%-4d", row[j]);
                }
                System.out.println();
            }
        }
    }
    //二维数组缓存优化 优化时间
    static class Triangle2 {
        private static void printSpacing(int n, int i) {
            int num = (n - 1 - i) * 2;
            for (int j = 0; j < num; j++) {
                System.out.print(" ");
            }
        }
        //将查询过得值存到二维数组中，如果查询过直接返回
        private static void print(int n) {
            int [] [] cache=new int[n][];
            for (int i = 0; i < n; i++) {
                cache[i]=new int[i+1];
                printSpacing(n, i);
                for (int j = 0; j <= i; j++) {
                    System.out.printf("%-4d", element(cache,i, j));
                }
                System.out.println();
            }
        }
        private static int element(int [][] cache,int i, int j) {
            if(cache[i][j]>0){
                return cache[i][j];
            }
            if (j == 0 || i == j) {
                cache[i][j]=1;
                return 1;
            }

            cache[i][j]= element(cache,i - 1, j - 1) + element(cache,i - 1, j);
            return cache[i][j];
        }
    }
    //递归实现
    static class Triangle1 {
        private static void printSpacing(int n, int i) {
            //输出空格个数
            int num = (n - 1 - i) * 2;
            for (int j = 0; j < num; j++) {
                System.out.print(" ");
            }
        }
        private static void print(int n) {
            for (int i = 0; i < n; i++) {
                printSpacing(n, i);
                for (int j = 0; j <= i; j++) {
                    System.out.printf("%-4d", element(i, j));
                }
                System.out.println();
            }
        }
        //获取元素
        private static int element(int i, int j) {
            if (j == 0 || i == j) {
                return 1;
            }
            return element(i - 1, j - 1) + element(i - 1, j);
        }
    }
}