力扣每日一道系列 --- LeetCode 160. 相交链表

在这里插入图片描述

📷 江池俊：个人主页 🔥个人专栏： ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人，再渺小也不会迷途。

LeetCode 160. 相交链表

在这里插入图片描述

思路：
首先计算两个链表的长度，然后判断两个链表的尾节点是否相同。如果不同，那么这两个链表就没有交集，返回空；如果相同，那么就通过计算两个链表的长度差，让长链表先走差距步，然后两个链表一起走，直到它们相遇。

具体步骤如下：

初始化两个指针 cur1 和 cur2 分别指向 headA 和 headB，即两个链表的头节点。同时，初始化两个变量 lenA 和 lenB 分别用来计算两个链表的长度。
通过循环计算 lenA 和 lenB，这里的循环是计算链表的长度，cur1 和 cur2 分别最后会指向链表的尾节点。
判断 cur1 和 cur2 是否相等，如果不同，说明两个链表没有交集，返回空。
如果 cur1 和 cur2 相等，说明两个链表有交集。这时需要确定哪个链表长，哪个链表短。长链表先走差距步，使两个链表的尾节点对齐。
通过循环让长链表先走差距步，这里的差距 n 是两个链表长度的差。
然后两个链表一起走，直到它们相遇。
当 longList 和 shortList 相遇时，返回相遇节点。

时间复杂度：O(m+n)
空间复杂度：O(1)

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *cur1 = headA;struct ListNode *cur2 = headB;int lenA = 1,lenB = 1;while(cur1->next)//计算第一个链表的长度{cur1 = cur1->next;lenA++;}while(cur2->next)//计算第二个链表的长度{cur2 = cur2->next;lenB++;}if(cur1!=cur2)//判断两个链表的尾节点是否相同{return NULL;}int n = abs(lenA-lenB);//得到差距步struct ListNode *longList = headA;struct ListNode *shortList = headB;if(lenA<lenB){longList = headB;shortList = headA;}while(n--)//先走差距步{longList = longList->next;}//一起走while(longList!=shortList){longList = longList->next;shortList = shortList->next;}return longList;
}