【Leedcode】数据结构中链表必备的面试题（第四期）

1.题目

160. 相交链表： 如下（示例）：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

1.判断两个链表是否相交？ 2.如果相交，求交点

2.思路+图解

(1)思路一

暴力求解-穷举法。依次取A链表中的每个节点跟B链表中的所有结点比较。
如果有相同的结点，就是相交，第一个相同的交点就是公共结点。这样做的时间复杂度为：O(N^2)
那么我们如何把时间复杂度优化到：O(N)

(2)思路二

1.尾结点相同就是相交，否则就不相交
2.求交点：长的链表先走（长度差）步，再同时走，第一个相同的结点就是交点，具体如下图

再这里要注意：可以用lenA和lenB去算两个链表的长度，方便求交点位置，如下图

3.源代码

代码如下（示例）：

struct ListNode 
{int val;struct ListNode *next;
};
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* pheadA = headA;struct ListNode* pheadB = headB;//先判断是否为环形结构int lenA = 1;while(pheadA -> next){lenA++;pheadA = pheadA -> next;}int lenB = 1;while(pheadB -> next){lenB++;pheadB = pheadB -> next;}if(pheadA != pheadB){return NULL;}int sub = abs(lenA - lenB);struct ListNode* longlist = headA;struct ListNode* shortlist = headB;if(lenA < lenB){longlist = headB;shortlist = headA;}//长的先走sub步while(sub--){longlist = longlist -> next;}//俩个开始一起走while(longlist != shortlist){longlist = longlist -> next;shortlist = shortlist -> next;}return longlist;
}

总结

以上就是今天要讲的内容，本文介绍数据结构中链表必备的面试题（第四期）
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！