文章目录
- 1.合并两个有序链表
- 双指针解决，大小节点的各放一个链表
- 2.单链表的分解
- 双指针解决，大小节点各一个链表，并断开原链表
- 3.合并 k 个有序链表
- 使用最小优先级队列，边poll边add，指针向前
- 4.单链表的倒数第 N 个节点
- 先找倒数第n个节点，再找n+1，删除即跳过n的值
- 5.单链表的中点
- 快慢指针，以快指针为空作为条件
- 6.判断链表是否包含环
- 快慢指针判断是否有环，慢指针重新指向头结点
- 7.两个链表是否相交
- 双指针解决，遍历完当前链表再拼接剩下链表遍历
- 8.附加的main代码
1.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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.单链表的分解
给你一个链表的头节点 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 个有序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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.length0 <= k <= 10^40 <= 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 个节点
给你一个链表，删除链表的倒数第 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 <= 300 <= Node.val <= 1001 <= 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.单链表的中点
给你单链表的头结点 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.判断链表是否包含环
给定一个链表的头节点 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.两个链表是否相交
给你两个单链表的头节点 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 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= 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;
}
}