2-链表-61-相交节点-LeetCode160
参考：代码随想录
LeetCode: 题目序号160
更多内容欢迎关注我（持续更新中，欢迎Star✨）
Github：CodeZeng1998/Java-Developer-Work-Note
技术公众号：CodeZeng1998（纯纯技术文）
生活公众号：好锅（Life is more than code）
CSDN: CodeZeng1998
其他平台：CodeZeng1998、好锅
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表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中节点数目为mlistB中节点数目为n1 <= 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 class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
/**
* 相交链表
*
* @param headA 第一个链表的头节点
* @param headB 第二个链表的头节点
* @return 返回相交节点，没有相交节点返回 null
* @author CodeZeng1998
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 计算链表长度
int headASize = 0;
int headBSize = 0;
ListNode headAListNode = headA;
ListNode headBListNode = headB;
while (headAListNode != null) {
headASize++;
headAListNode = headAListNode.next;
}
while (headBListNode != null) {
headBSize++;
headBListNode = headBListNode.next;
}
headAListNode = headA;
headBListNode = headB;
// 将较长的链表替换成固定的一个
if (headASize < headBSize) {
int tempSize = headASize;
headASize = headBSize;
headBSize = tempSize;
ListNode tempListNode = headAListNode;
headAListNode = headBListNode;
headBListNode = tempListNode;
}
// 较长的链表优先移动长度差个位置
for (int i = 0; i < headASize - headBSize; i++) {
headAListNode = headAListNode.next;
}
// 查找是否有相同的节点，有：返回对应节点，无：返回 null
while (headAListNode != null) {
if (headAListNode == headBListNode) {
return headAListNode;
} else {
headAListNode = headAListNode.next;
headBListNode = headBListNode.next;
}
}
return null;
}
ChatGPT：
这段代码是用来找到两个链表的交点的方法。让我们逐步解释：
- 初始化两个变量
headASize和headBSize，用于存储两个链表的大小，初始值为0。 - 创建两个临时的ListNode变量
headAListNode和headBListNode，并将它们设置为各自链表的头节点。 - 使用两个while循环遍历每个链表并计算每个链表的节点数。这通过在达到末尾（空节点）之前遍历列表并递增相应的大小变量来完成。
- 计算大小后，将临时的ListNode变量重置为链表的头部。
- 如果第一个链表（
headASize）的大小小于第二个链表（headBSize）的大小，则交换两个大小。此外，交换ListNode变量以确保headAListNode指向较长的链表，headBListNode指向较短的链表。 - 使用for循环将
headAListNode向前移动两个链表之间的差值大小。这一步确保了从交点开始，两个列表剩余的节点数相同。 - 最后，使用while循环同时迭代两个列表，直到找到交点（即
headAListNode等于headBListNode）或其中一个列表到达末尾（空节点）。如果找到交点，则返回交点节点。如果未找到交点，则返回null。
总的来说，该算法确保从与交点的相同相对位置开始遍历两个链表，从而有效地检测交点节点。
160. Intersection of Two Linked Lists
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Custom Judge:
The inputs to the judge are given as follows (your program is not given these inputs):
intersectVal- The value of the node where the intersection occurs. This is0if there is no intersected node.listA- The first linked list.listB- The second linked list.skipA- The number of nodes to skip ahead inlistA(starting from the head) to get to the intersected node.skipB- The number of nodes to skip ahead inlistB(starting from the head) to get to the intersected node.
The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.
Example 2:
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
Constraints:
- The number of nodes of
listAis in them. - The number of nodes of
listBis in then. 1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA < m0 <= skipB < nintersectValis0iflistAandlistBdo not intersect.intersectVal == listA[skipA] == listB[skipB]iflistAandlistBintersect.
Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?
更多内容欢迎关注我（持续更新中，欢迎Star✨）
Github：CodeZeng1998/Java-Developer-Work-Note
技术公众号：CodeZeng1998（纯纯技术文）
生活公众号：好锅（Life is more than code）
CSDN: CodeZeng1998
其他平台：CodeZeng1998、好锅
