西安营销型网站建站,wap手机网站开发软件,帮做钓鱼网站会怎样,网站建设案例包括哪些题目 思路
1.哈希集合
因为要求是否存在相交节点#xff0c;那么我们就可以利用哈希集合先将listA链表里面的所有数据存入#xff0c;然后访问listB#xff0c;判断其是否有节点在哈希集合中#xff0c;若存在#xff0c;则说明此节点为相交的节点。若遍历完之后仍没有发…题目 思路
1.哈希集合
因为要求是否存在相交节点那么我们就可以利用哈希集合先将listA链表里面的所有数据存入然后访问listB判断其是否有节点在哈希集合中若存在则说明此节点为相交的节点。若遍历完之后仍没有发现则说明两个表之间不存在相交节点返回nullptr即可。
2.双指针
首先进行条件判断若headA和headB中有一个为空则说明不可能有相交节点直接返回nullptr即可。
接着用cur1和cur2变量用来遍历listA和listB链表循环中用了三元运算符就第一个来说若cur1为空则直接将cur1赋值为headB,若不为空则继续往下移动。
第二个也是如此那为什么这样就可以求出它们的相交节点呢
假设链表 headA 的长度为 m链表 headB 的长度为 n且它们的交点之后的公共部分长度为 k。 当 cur1 遍历完 headA 后它会开始遍历 headB此时 cur1 已经走了 m 步。 当 cur2 遍历完 headB 后它会开始遍历 headA此时 cur2 已经走了 n 步。 当 cur1 和 cur2 都开始遍历对方的链表时它们会在交点处相遇因为此时 cur1 和 cur2 都走了 m n - k 步。
如果两个链表没有交点那么 cur1 和 cur2 最终都会指向 nullptr此时返回 nullptr。 下面举个例子来看就容易理解了
listA: A1 - A2 - A3 - C1 - C2 - C3
listB: B1 - B2 - C1 - C2 - C3 链表 listA 的长度为 m 6。 链表 listB 的长度为 n 5。 交点之后的公共部分长度为 k 3即 C1 - C2 - C3。
运行过程 初始化指针 cur1 指向 A1。 cur2 指向 B1。 遍历过程 cur1 依次遍历A1 - A2 - A3 - C1 - C2 - C3 - nullptr。 当 cur1 到达 nullptr 时它已经走了 m 6 步然后切换到 listB继续遍历B1 - B2 - C1。 cur2 依次遍历B1 - B2 - C1 - C2 - C3 - nullptr。 当 cur2 到达 nullptr 时它已经走了 n 5 步然后切换到 listA 继续遍历A1 - A2 - A3 - C1。 相遇点 当 cur1 切换到 listB 后它走了 m n - k 6 5 - 3 8 步。 当 cur2 切换到 listA 后它走了 n m - k 5 6 - 3 8 步。 两者会在交点 C1 处相遇。
代码
1.哈希集合
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_setListNode* s;while(headA){s.insert(headA);headA headA-next;}while(headB){if(s.count(headB)){return headB;}headB headB-next;}return nullptr;}
};
2.双指针
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA nullptr || headB nullptr)return nullptr;ListNode* cur1 headA;ListNode* cur2 headB;while(cur1 ! cur2){cur1 cur1nullptr ? headB : cur1-next;cur2 cur2nullptr ? headA : cur2-next;}return cur1;}
};
