数据结构-相交链表OJ-如何用环形链表来解决相交链表？

---

前言

本篇讲解相交链表

相交链表

这道题目我们有多种思路去解决，也可以暴力解法，本篇只讲解时间复杂度为 O(m + n) 、空间复杂度 O(1) 的其中的两种解决方案

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

法一、快慢法

法一思路的思想类似于快慢指针，但并不相同

具体操作是先分别遍历一次两个链表，分别得到长度为a和b，之后计算a - b的绝对值，也就是两个链表之间相差的长度，记为len，之后让长链表先走相差步（len步），之后长链表和短链表同时走，一次走一步，如果相同就停止，最后返回长链表（短链表也可以），无论为空或者有相交结点都是正确的

法二、构建环形链表

该法来源于环形链表的扩展结论——当一个环形链表定义一个快指针一个慢指针进行遍历时，两个指针总会相遇，之后我们在相遇点断开链表的链接，一个从相遇点开始走，一个从链表起始点开始走，最后会在环的起始点相遇，后续证明详见环形链表篇

而对于这道题，我们将两个链表链接起来形成环形链表，就可以进行上述操作来判断是否有交点，如果没有交点，最后仍旧会走到空，如果有，那就结束

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if (headA == NULL || headB == NULL) return NULL;struct ListNode* tailB = headB;while (tailB->next != NULL) {tailB = tailB->next;}tailB->next = headA;struct ListNode* slow = headB;struct ListNode* fast = headB;int hasCycle = 0;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) {hasCycle = 1;break;}}if (hasCycle) {slow = headB; while (slow != fast){slow = slow->next;fast = fast->next;}if(slow){tailB->next = NULL;return slow;}}tailB->next = NULL;return NULL;
}

总结

今天讲解了能够将时间复杂度为控制在 O(m + n) 、空间复杂度 控制在O(1) 的解决相交链表的两种解法