企业官网建设流程全解析

网站备案 信息安全管理协议,数字化营销方案,实名网站空间,网站做端口是什么问题思路暴力法: 你看到题目#xff0c;其实就是判断是否有两个元素相同#xff0c;暴力法#xff0c;对于链表A中的每一个节点#xff0c;遍历链表B的所有节点#xff0c;检查是否有节点地址相同的。时间复杂度: O(L_A * L_B)空间复杂度: O(1)/*** Definition for singly-lin…思路暴力法:你看到题目其实就是判断是否有两个元素相同暴力法对于链表A中的每一个节点遍历链表B的所有节点检查是否有节点地址相同的。时间复杂度: O(L_A * L_B)空间复杂度: O(1)/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { // 暴力法 // 先判断边界情况 if (headA nullptr || headB nullptr) { return nullptr; } // 固定遍历 // 初始节点 ListNode *ptA headA; //flag 标志是否找到 while (ptA ! nullptr) { ListNode *ptB headB; while (ptB ! nullptr) { if (ptB ptA) { return ptB; } ptB ptB-next; } ptA ptA-next; } return nullptr; } };哈希集合法其实很多判断两者是否相等的都可以使用hash集合因为hash的特点就是取值时间复杂度为O(1). 我们可以先遍历A链表把这个链表的所有节点的地址存储到hash中然后再遍历链表B,依次判断是否有节点地址和A中的相同。时间复杂度: O(L_A L_B)空间复杂度: O(L_A) # 因为存储了hash/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { // 哈希集合法 find, count, insert 时间复杂度为O(1) // 先判断边界情况 if (headA nullptr || headB nullptr) { return nullptr; } // 定义集合 unordered_setListNode* nodeset; // 遍历链表A ListNode *ptA headA; while (ptA ! nullptr) { if (nodeset.find(ptA) nodeset.end()) { nodeset.insert(ptA); ptA ptA - next; } } // 遍历链表B ListNode *ptB headB; while (ptB ! nullptr) { if (nodeset.find(ptB) ! nodeset.end()) { return ptB; } ptB ptB-next; } return nullptr; } };倒序法因为如果两个链表相交了那么他们在链表的末端肯定也是重叠的那么其实我只要判断最后一个节点是否相等就知道是否相交了但是也需要找到相交的起点如果可以倒着遍历就解决了换一个想法我可以正向遍历的时候用vector分别把A,B链表的节点地址存储下来然后倒着对齐遍历这两个vector一旦开始不相等那么前一个地址就是相交点时间复杂度: O(LALB)空间复杂度: O(LALB)长度差法这个方法其实和倒序法基本一样也是考虑末端是重叠的那么我只要计算出两个链表的长度然后将长链表的起点前移使得两个链表的剩余长度相等最后再同步遍历寻找交点。时间复杂度: O(LALB)空间复杂度: O(1)/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { // 长度差法 // 先判断边界情况 if (headA nullptr || headB nullptr) { return nullptr; } // 遍历A ListNode *ptA headA; ListNode *ptB headB; int length_A 0; int length_B 0; while (ptA ! nullptr) { length_A length_A 1; ptA ptA - next; } while (ptB ! nullptr) { length_B length_B 1; ptB ptB - next; } int diff length_A - length_B; ListNode *longer headA; ListNode *shorter headB; if (length_A length_B) { longer headB; shorter headA; diff -1 * diff; } // 让长的先走 for (int i 0; i diff; i) { longer longer-next; } while(longer ! nullptr) { if (longer shorter) { return longer; } longer longer-next; shorter shorter-next; } return nullptr; } };方法双指针法由于相交那么当A链表走完之后还走B链表B链表走完之后还走A链表的话并且他们同时出发那么如果有交点那么肯定在交点出相遇/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { // 长度差法 // 先判断边界情况 if (headA nullptr || headB nullptr) { return nullptr; } ListNode *ptA headA; ListNode *ptB headB; while (ptA ! ptB) { ptA (ptA nullptr) ? headB : ptA-next; ptB (ptB nullptr) ? headA : ptB-next; } return ptA; // 因为遍历完成后要么就是要的交点要么就是nullptr. } };