leetcode hot100刷题日记——11.相交链表

解答：

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//方法一：先遍历一条链表，存节点；再遍历另一条链表，找对应的节点有没有存过// unordered_set<ListNode*>vis;// ListNode *temp=headA;// while(temp!=nullptr){//     vis.insert(temp);//     temp=temp->next;// }// temp=headB;// while(temp!=nullptr){//     if(vis.count(temp)!=0){//         return temp;//     }//     temp=temp->next;// }// return nullptr;//方法二：双指针if(headA==nullptr || headB==nullptr){return nullptr;}ListNode *pA=headA,*pB=headB;while(pA!=pB){pA=pA==nullptr?headB:pA->next;pB=pB==nullptr?headA:pB->next;}return pB;}
};

方法一：
时间复杂度O(M+N)
空间复杂度O(N)

方法二：
时间复杂度O(M+N)
空间复杂度O(1)

方法二思想详见官方题解link

直白理解：两个链表左端对齐，后面的分别用对方的给补上，如果两个一样长，那就不用找到后面补上的部分；如果不一样长，分别经过对方的补上之后相同的部分就能拉齐了