建设一个视频网站首页,西安建站模板厂家,品牌网站运营,wordpress ip被禁用给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null 。
图示两个链表在节点 c1 开始相交#xff1a; 题目数据 保证 整个链式结构中不存在环。
注意#xff0c;函数返回结果后请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 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 中第四个节点) 在内存中指向相同的位置。
思路 两个指针分别指向两个链表表头依次遍历判断两个指针指向的结点是否相等若一方结点走到末尾为空后指向另一个链表的头结点接着遍历比较经过数学分析最多遍历mn次即可获得相交结点或者不存在相交结点。
#include iostream
#include algorithm
#include vector
#include unordered_map
using namespace std;struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}
};
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {if (headA nullptr || headB nullptr)return nullptr;ListNode* pa headA;ListNode* pb headB;while (pa ! nullptr || pb ! nullptr)//走的次数一样 所以最后都停在nullptr{if (pa pb)return pa;//判断是否相同 相同代表有交点if (pa nullptr)pa headB;elsepa pa-next;//每次pa只移动一次 if (pb nullptr)pb headA;else pb pb-next;//每轮pb只移动一次}return nullptr;//没有交点
}
int main() {ListNode node1, node2, node3, node4, node5, node6, node7, node8;node1.val 4;node1.next node2;node2.val 1;node2.next node3;node3.val 8;node3.next node4;node4.val 4;node4.next node5;node5.val 5;node5.next nullptr;node6.val 5;node6.next node7;node7.val 6;node7.next node8;node8.val 1;node8.next node3;ListNode* res getIntersectionNode(node1, node6);if (res){cout res-val endl;}else {cout no intersection node endl;}return 0;
}
