一文学会链表双指针技巧

1.合并两个有序链表

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 定义虚拟头节点以及指针
        ListNode dummy = new ListNode(0), p = dummy;
        ListNode p1 = list1, p2 = list2;
        // 当给定的两个链表不为空时，表示链表的节点没有遍历完
        while (p1 != null && p2 != null) {
            // 比较.val即节点的值，将较小的值放在p2
            if (p1.val > p2.val) {
                // p2节点赋值给p的下一个节点
                p.next = p2;
                // p2指针不断前进
                p2 = p2.next;
                // 将较大的值放在p1
            } else {
                p.next = p1;
                // p1指针不断前进
                p1 = p1.next;
            }
            // p指针不断前进
            p = p.next;
        }

        //
        /*
        当不满足循环跳出时，表示p1与p2同时不为空，再进行分开判断;
        如果此时p1单独不为空，p2一定为空，意味着p1比p2的长度长;
        再由于p1是升序链表，后面的节点只会比前面的节点大，所以直接拼接到p指针的下一个节点即可
         */
        if (p1 != null) {
            p.next = p1;
        }

        // 与上面同理
        if (p2 != null) {
            p.next = p2;
        }

        // 去除虚拟头节点返回
        return dummy.next;
    }

这是一个简单难度的题，其中使用到了一个双指针算法中常用到的虚拟头结点（Dummy Node）技巧。

虚拟头结点是一个额外的节点，不存储任何实际的值。它位于实际链表的头结点之前，并链接到实际链表的头结点。通过引入虚拟头结点，我们可以避免对头结点进行特殊处理，从而使代码更加简洁和易于理解。

什么时候需要用虚拟头结点？

当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。

• 时间复杂度分析
  最差情况下：在最坏情况下，两个给定链表的长度都为 n。在遍历两个链表并比较节点值的过程中，每次都选择较小的值进行拼接，并移动对应的指针。因此，需要遍历全部的 n 个节点，并将它们逐个拼接起来。所以，在最坏情况下，时间复杂度为 O(n)。
  最好情况下：在最好情况下，其中一个给定链表为空，即其中一个链表的长度为 0。此时，另一个链表的所有节点直接拼接到结果链表中，无需进行任何比较和移动操作。因此，时间复杂度为 O(1)。

一句话记解法

双指针解决，大小节点的各放一个链表

2.单链表的分解

86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

再解释一下题目，示例1中原链表为 1 -> 4 -> 3 -> 2 -> 5 -> 2，指定数为3，要求是将3右边比3小的数移到左边来，其他数字不变，也就是将右边的两个2移到左边过来；左边要求为1 -> 2 -> 2 ->4 而不是1 -> 4 -> 2 -> 2的因为，题目要求所有小于3的节点要出现在大于或者等于3的节点之前，这里的4 大于 3了，所以要在4的前面

public ListNode partition(ListNode head, int x) {
        ListNode leftNode = new ListNode(0), rightNode = new ListNode(0);
        ListNode p = head, p1 = leftNode, p2 = rightNode;
        // 当节点不为空时结束循环
        while (p != null) {
            // 将比指定值大的节点放在右边链表
            if (p.val >= x) {
                p2.next = p;
                p2 = p2.next;
            } else {
                p1.next = p;
                p1 = p1.next;
            }
            /*
            在这个过程中，p指针指向当前处理的节点，temp指向下一个待处理的节点;
            将p指向temp，就可以断开p节点的next指针;
            将p的下个节点置空，并作为下次循环的入参
             */
            ListNode temp = p.next;
            p.next = null;
            p = temp;

        }
        p1.next = rightNode.next;
        return leftNode.next;
    }

这个题属于中等难度的题，这里是直接使一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x，处理方法与上面合并两个有序链表的非常相似。

• 时间复杂度分析
  最差情况下：在最坏情况下，即链表中的所有节点都需要被遍历，并且每个节点都需要被移动到新的链表中。因此，时间复杂度为 O(n)，其中 n 表示链表的长度。
  最好情况下：在最好情况下，即链表已经按照给定值进行了分区，不需要进行任何操作，只需返回原始链表。因此，时间复杂度为 O(1)。

一句话记解法

双指针解决，大小节点各一个链表，并断开原链表

3.合并 k 个有序链表

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

public ListNode mergeKLists(ListNode[] lists) {
        // 注意为空的判断不能丢
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆(a.val - b.val)为最小堆,(b.val - a.val)为最大堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));
        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }

        // 因为每次poll会弹出节点，当pq中所有节点弹出时，循环结束
        while (!pq.isEmpty()) {
            // 获取最小节点所在的整个链表，并将其弹出pq
            ListNode node = pq.poll();
            // 不断的连接最小值，拼接结果
            p.next = node;
            // 判断最小节点所在的链表下面是否还有其他节点，如果有的话，就再把剩下的也就是node.next再放回去
            if (node.next != null) {
                /*
                这里如果输入3组数据
                那么pq每一次循环只有2组数组，并且其中变化的1组数组，较于上一次循环少了最小值(被弹出);
                另外的一组被poll拉出来赋值给p.next，并被弹出最小堆
                 */
                pq.add(node.next);
            }
            //p指针不断前进
            p = p.next;
        }
        return dummy.next;
    }

这是一道困难难度的题，这里使用到优先级队列（二叉堆）这种数据结构的解法，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点

优先级队列是一种特殊的数据结构，它可以存储具有优先级的元素，并且每次取出的元素都是具有最高（或最低）优先级的元素。

二叉堆是一种常见的实现优先级队列的数据结构。它是一个完全二叉树（即除了最后一层外，所有层都被填满，且最后一层从左到右连续填充），并且满足堆属性：对于最小堆来说，父节点的值总是小于或等于其子节点的值；对于最大堆来说，父节点的值总是大于或等于其子节点的值。

在 Java 中，优先级队列（二叉堆）的实现是通过 java.util.PriorityQueue 类来实现的。它是 Java 集合框架提供的一种数据结构，用于实现优先级队列。

上面有用到PriorityQueue中的add和poll方法

• add(element) 方法用于将指定的元素添加到优先级队列中。它将元素插入到队列的末尾，并根据元素的优先级进行调整，以使堆属性得到维护。
• poll() 方法用于从优先级队列中弹出并返回队列中具有最高（或最低）优先级的元素。它首先移除队列的顶部元素，然后根据堆属性将新的顶部元素下移至正确位置，以维持堆的性质。如果队列为空，则返回 null
• 时间复杂度分析
  最差情况下：在最差情况下，即所有链表的总长度为 n，每次从优先级队列中弹出节点需要 O(logk) 的时间复杂度。而在总共有 n 个节点的情况下，有 O(n) 次循环迭代。因此，最差情况下的时间复杂度为 O(n logk)
  最好情况下：在最好情况下，即其中一个链表为空，直接返回空结果，时间复杂度为 O(1)

一句话记解法

使用最小优先级队列，边poll边add，指针向前

4.单链表的倒数第 N 个节点

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

假设链表的长度为l，我们要找到倒数第n个节点，倒数第n个节点就是正数第l-n+1个节点; 先让p1走n步; p1再走l-n步就到了末尾不存在的空指针,同时让p2从头结点开始走l-n步,p2就停留在了第l-n+1个节点上，即倒数第n个节点;举例说明，1 -> 2 -> 3 -> 4 -> 5 -> 6 链表长度l=6，找倒数第n=2个节点，即正数第6-2+1=5个节点; 先让p1走2步，由于指针p初始位置在节点1，所以到达节点3; p1再走6-2=4步就到了末尾不存在的空指针,同时让p2从头结点开始走6-2=4步,p2就停留在了第6-2+1=5个节点上，即倒数第2个节点;最后需要注意的是，我们删除导数第n个节点时，需要先找到导数第n+1个节点才能进行删除，所以代码中使用到n的地方，我们写为n+1

public ListNode removeNthFromEnd(ListNode head, int n) {
        // 删除节点，这里采用虚拟头结点比较合适
        ListNode dummy = new ListNode(0);
        // 将要删除的节点拼到虚拟头结点后
        dummy.next = head;
        ListNode p1 = dummy, p2 = dummy;
        // 要删除倒数第n个节点，得先找到n+1个节点，n+1表示，遍历到要删除节点的前一个节点
        for (int i = 0; i < n + 1; i++) {
            p1 = p1.next;
        }
        // p1为空的时候停下，表示链表遍历完了
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        // 将倒数第n个节点的值跳过，直接连接到再下一个节点，完成删除第n节点的操作
        p2.next = p2.next.next;

        return dummy.next;
    }

便于理解代码也能写成两个方法

public ListNode findFromNode(ListNode node, int n) {
        ListNode p1 = node,p2 = node;
        // 找到倒数第n个节点
        for (int i = 0; i < n; i++) {
            p1 = p1.next;
        }
        // p1为空的时候停下，表示链表遍历完了
        while (p1 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        return p2;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 删除节点，这里采用虚拟头结点比较合适
        ListNode dummy = new ListNode(0);
        // 将要删除的节点拼到虚拟头结点后
        dummy.next = head;
        // 注意，这里传参不要写成head
        ListNode p2 = findFromNode(dummy, n + 1);
        // 将倒数第n个节点的值跳过，直接连接到再下一个节点，完成删除第n节点的操作
        p2.next = p2.next.next;
        return dummy.next;
    }

这是一道中等难度的题，可能你会说，这里只需要先for循环得出长度，然后再for循环将倒数第n个节点，转换为整数第l-n+1个节点就行，l表示链表的长度，没错这样是可以的。但是如果是出现在面试中，面试官更希望你能用一次遍历解决

• 时间复杂度分析
  最差情况下：在最差情况下，链表的长度为N，要删除的节点位于链表的末尾。在这种情况下，算法需要遍历完整个链表，以找到要删除节点的前一个节点。因此，遍历的时间复杂度为O(N)
  最好情况下：在最好情况下，链表的长度为N，要删除的节点位于链表的开头。在这种情况下，算法只需要遍历一次即可找到要删除节点的前一个节点，并进行删除操作。因此，遍历的时间复杂度为O(1)

一句话记解法

先找倒数第n个节点，再找n+1，删除即跳过n的值

5.单链表的中点

876.链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

public ListNode middleNode(ListNode head) {
        // 快慢指针
        ListNode slow = head, fast = head;
        // 这里只要通过快指针来判断是否到达末尾即可，要同时2个节点不为空才循环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 直接返回慢指针则为链表的中点
        return slow;
    }

这是一道简单难度的题，问题的关键在于同时使用两个快慢指针，每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。当链表长度为奇数时，慢指针 slow 恰好指向链表的中间节点。当链表长度为偶数时，慢指针 slow 将会停在中间两个节点的第二个节点上

• 时间复杂度分析
  最差情况下： 在最差情况下，链表的长度为N。由于快指针每次移动两个节点，慢指针每次移动一个节点，所以当快指针到达链表末尾时，慢指针正好位于中间节点。因此，整个过程需要遍历整个链表一次。所以，时间复杂度为O(N)
  最好情况下： 在最好情况下，链表的长度为N。如果链表长度为奇数，那么快指针会比慢指针先到达末尾，而慢指针正好位于中间节点。如果链表长度为偶数，那么快指针会比慢指针先到达倒数第二个节点，而慢指针正好位于中间的两个节点中的第一个。无论是奇数还是偶数，算法只需要遍历一次即可找到中间节点。因此，时间复杂度为O(N)

一句话记解法

快慢指针，以快指针为空作为条件

6.判断链表是否包含环

142.环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

public ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 如果快慢指针相遇说明在进行无限循环即存在环
            if (fast == slow) break;

        }
        // 当上面退出循环后，看是否遇到空指针，遇到了就代表没有环
        if (fast == null || fast.next == null) {
            return null;
        }

        // 慢指针重新指向头节点
        slow = head;

        // 快慢指针同步前进，当两个指针相等时，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

这是一道中等难度的题，属于一个经典问题，属于上面单链表的中点的延伸，在快慢指针相遇的情况下说明一定有环，重新将慢指针指向头结点后，相交点就是环的起点了

• 时间复杂度分析
  最差情况下： 在最差情况下，链表中存在环，且环的长度为N。快指针每次移动两个节点，慢指针每次移动一个节点，直到它们相遇为止。在这种情况下，整个过程需要遍历整个链表以确定是否存在环，这需要O(N)的时间复杂度。之后，当慢指针重新指向头节点后，快指针和慢指针再次同步前进，直到它们相遇在环的起点。由于环的长度为N，所以在最坏情况下，这部分过程需要再次遍历整个环，时间复杂度为O(N)。因此，最坏情况下的总时间复杂度为O(N)
  最好情况下： 在最好情况下，链表中不存在环，即链表是一个单链表。在这种情况下，快指针会先到达链表末尾，而慢指针会到达链表的最后一个节点。因此，在第一次循环中，算法就会检测到快慢指针相遇，然后返回null，表示没有环存在。所以，在最好情况下，算法只需要遍历一次链表。因此，最好情况下的时间复杂度为O(N)

一句话记解法

快慢指针判断是否有环，慢指针重新指向头结点

7.两个链表是否相交

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

**进阶：**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        // 这题思路比较清洗和简单，将两个链表连起来即可，两个指针相遇时表示找到了相交的节点
        while (p1 != p2) {
            if (p1 != null)
                p1 = p1.next;
                // p1为空后就连上headB
            else
                p1 = headB;
            if (p2 != null)
                p2 = p2.next;
                // p2为空后就连上headA
            else
                p2 = headA;
        }
        // 返回任意一个指针即可
        return p1;
    }

这是一道比较简单的题目，题目描述的还是比较清晰的，解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1

• 时间复杂度分析

在最差情况下，即两个链表没有相交的节点。首先需要遍历整个链表 headA，然后将指针 p1 连接到链表 headB 的头部，继续遍历整个链表 headB。接着，需要再次遍历整个链表 headA。因此，在最差情况下，需要进行三次完整的链表遍历，时间复杂度为 O(m + n)，其中 m 和 n 分别表示两个链表的长度

在最好情况下，即两个链表的首节点就是相交的节点。首先需要一次遍历就可以找到相交的节点，即指针 p1 和 p2 相遇。因此，在最好情况下，时间复杂度为 O(1)

一句话记解法

双指针解决，遍历完当前链表再拼接剩下链表遍历

8.附加的main代码

笔者喜欢将算法代码写完后，放到编译器的main里面去跑，方便debug去分析和学习。1-5题放在main中是比较简单的，直接创建链表调用算法的方法打印即可，这里给出第5题作为示例，1-4题同理，主要是6,7题，下面main中的输入均为力扣运行时所有的测试案例

5.单链表的中点

package blog.linkedlist;


/**
 * @Author Daniel
 * @Date: 2023/08/14 16:00
 * @Description LeetCode876.链表的中间结点
 **/
public class MiddleNode {

    public ListNode middleNode(ListNode head) {
        // 快慢指针
        ListNode slow = head, fast = head;
        // 这里只要通过快指针来判断是否到达末尾即可，要同时2个节点不为空才循环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 直接返回慢指针则为链表的中点
        return slow;
    }


    public static void main(String[] args) {
        int[] testCase1 = {1, 2, 3, 4, 5};
        int[] testCase2 = {1, 2, 3, 4, 5, 6};
        MiddleNode middleNode = new MiddleNode();
        middleNode.print(middleNode.middleNode(middleNode.array2ListNode(testCase1)));
//        middleNode.print(middleNode.middleNode(middleNode.array2ListNode(testCase2)));
    }

    public ListNode array2ListNode(int[] arr) {
        ListNode root = new ListNode(0);
        ListNode other = root;
        for (int j : arr) {
            ListNode node = new ListNode(j);
            other.next = node;
            other = node;
        }
        return root.next;
    }

    public void print(ListNode node) {
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }


}

6.判断链表是否包含环

package blog.linkedlist;


/**
 * @Author Daniel
 * @Date: 2023/08/14 16:00
 * @Description LeetCode142.环形链表 II
 **/
public class DetectCycle {

    public ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 如果快慢指针相遇说明在进行无限循环即存在环
            if (fast == slow) break;

        }
        // 当上面退出循环后，看是否遇到空指针，遇到了就代表没有环
        if (fast == null || fast.next == null) {
            return null;
        }

        // 慢指针重新指向头节点
        slow = head;

        // 快慢指针同步前进，当两个指针相等时，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    public static void main(String[] args) {
        DetectCycle detectCycle = new DetectCycle();
        // 输入链表与环的位置
        int[] testCase1Num1 = {3, 2, 0, -4};
        int[] testCase1Num2 = {1, 2};
        int[] testCase1Num3 = {1};
        int testCase1Pos1 = 1;
        int testCase1Pos2 = 0;
        int testCase1Pos3 = -1;
        // 创建链表
        ListNode head = buildLinkedList(testCase1Num1, testCase1Pos1);
//        ListNode head = buildLinkedList(testCase1Num2, testCase1Pos2);
//        ListNode head = buildLinkedList(testCase1Num3, testCase1Pos3);
        ListNode result = new DetectCycle().detectCycle(head);
        // 输出结果
        if (result != null) {
            int index = detectCycle.getIndex(head, result);
            System.out.println("tail connects to node index " + index);
        } else {
            System.out.println("no cycle");
        }

    }


    // 构建链表
    private static ListNode buildLinkedList(int[] nums, int pos) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        ListNode cycleNode = null;

        for (int i = 0; i < nums.length; i++) {
            curr.next = new ListNode(nums[i]);
            curr = curr.next;

            if (i == pos) {
                cycleNode = curr;
            }
        }

        // 尾部连接到指定位置，形成环
        curr.next = cycleNode;

        return dummy.next;
    }

    private int getIndex(ListNode head, ListNode node) {
        int index = 0;
        ListNode current = head;
        while (current != node) {
            current = current.next;
            index++;
        }
        return index;
    }

    public void print(ListNode node) {
        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }
    }


}

7.两个链表是否相交

package blog.linkedlist;

/**
 * @Author Daniel
 * @Date: 2023/08/14 16:00
 * @Description LeetCode160.相交链表
 **/
public class GetIntersectionNode {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        // 这题思路比较清洗和简单，将两个链表连起来即可，两个指针相遇时表示找到了相交的节点
        while (p1 != p2) {
            if (p1 != null)
                p1 = p1.next;
                // p1为空后就连上headB
            else
                p1 = headB;
            if (p2 != null)
                p2 = p2.next;
                // p2为空后就连上headA
            else
                p2 = headA;
        }
        // 返回任意一个指针即可
        return p1;
    }

    public ListNode[] createInput(ListNode headA, ListNode headB, int skipA, int skipB) {
        // 连起来
        ListNode a = headA, b = headB;
        // 循环到相交节点
        for (int i = 0; i < skipA; i++) {
            a = a.next;
        }
        for (int i = 0; i < skipB; i++) {
            b = b.next;
        }

        if (a == null || b == null)
            return null;

        // b回去，重新给b的相交部分赋值，保证链表地址也相同
        b = headB;
        // 由于a中已经包含了相交点，这里只需要循环到skipB - 1即可
        for (int i = 0; i < skipB - 1; i++) {
            b = b.next;
        }
        // 重新给相交部分赋值
        b.next = a;

        return new ListNode[]{headA, headB};

    }

    public static void main(String[] args) {
        GetIntersectionNode getIntersectionNode = new GetIntersectionNode();
        // 这里如果非要用数组转链表，需要保证他们相交链表的的地址都是一样的，不仅仅是值，否则就直接用ListNode.next连接的方式创建
        ListNode testCase1A = getIntersectionNode.array2ListNode(new int[]{4, 1, 8, 4, 5});
        ListNode testCase1B = getIntersectionNode.array2ListNode(new int[]{5, 6, 1, 8, 4, 5});
        int testCase1SkipA = 2;
        int testCase1SkipB = 3;
        ListNode testCase2A = getIntersectionNode.array2ListNode(new int[]{1, 9, 1, 2, 4});
        ListNode testCase2B = getIntersectionNode.array2ListNode(new int[]{3, 2, 4});
        int testCase2SkipA = 3;
        int testCase2SkipB = 1;
        ListNode testCase3A = getIntersectionNode.array2ListNode(new int[]{2, 6, 4});
        ListNode testCase3B = getIntersectionNode.array2ListNode(new int[]{1, 5});
        int testCase3SkipA = 3;
        int testCase3SkipB = 2;

        ListNode[] input = new GetIntersectionNode().createInput(testCase1A, testCase1B, testCase1SkipA, testCase1SkipB);
//        ListNode[] input = new GetIntersectionNode().createInput(testCase2A, testCase2B, testCase2SkipA, testCase2SkipB);
//        ListNode[] input = new GetIntersectionNode().createInput(testCase3A, testCase3B, testCase3SkipA, testCase3SkipB);
        if (input != null) {
            ListNode intersectionNode = new GetIntersectionNode().getIntersectionNode(input[0], input[1]);
            // 输出结果
            if (intersectionNode != null) {
                System.out.println("Intersected at '" + intersectionNode.val + "'");
            } else {
                System.out.println("No intersection");
            }
        } else {
            System.out.println("No intersection");
        }


    }

    public ListNode array2ListNode(int[] arr) {
        ListNode root = new ListNode(arr[0]), other = root;
        for (int i = 1; i < arr.length; i++) {
            ListNode temp = new ListNode(arr[i]);
            other.next = temp;
            other = temp;
        }
        return root;
    }
}