LeetCode-160.相交链表
160. 相交链表[1]
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 图示两个链表在节点 c1 开始相交：
image.png
方法一：哈希表法
//相交链表哈希表法
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
{if (headA == NULL || headB == NULL) return NULL;unordered_set<ListNode*> st;//1：首先把headA插入st容器中while (headA != NULL){st.insert(headA);headA = headA->next;}//2:判断headB当前值是否在容器中while (headB!=NULL){if (st.count(headB)) return headB;headB = headB->next;}return nullptr;
}方法二：环形查找
image.png
1：假如有相交的点 A走到C的距离是：a+c+b:2+2+3 B走到C的距离是：b+c+a:3+2+2 2:假如没有相交的点 那么A与B走的距离都是：a+b 3:当A等于B时候返回，或者都为null时候跳出循环
//取环形链表的方法
ListNode* getIntersectionNode1(ListNode* headA, ListNode* headB)
{if (headA == NULL || headB == NULL) return NULL;ListNode* tempa = headA;ListNode* tempb = headB;while (tempa != tempb) //只有找到相等或者找不到都为null时候跳出循环{tempa = tempa != nullptr ? tempa->next : headB;tempb = tempb != nullptr ? tempb->next : headA;}return tempa; //返回tempa或者tempb都可以
}最新原创的文章都先发布在公众号，欢迎关注哦~， 扫描下方二维码回复「资料」可以获得我汇总整理的计算机学习资料
扫码_搜索联合传播样式-标准色版.png
引用链接
[1] 160. 相交链表: https://leetcode.cn/problems/intersection-of-two-linked-lists/