网络公司除了做网站,网络推广公司名称大全,58同城一样的网站怎样建设,今天的热点新闻一.前言
今天在力扣上刷到了一道题#xff0c;想着和大家一起分享一下这道题——相交链表https://leetcode.cn/problems/intersection-of-two-linked-lists废话不多说#xff0c;让我们开始今天的分享吧。
二.正文
1.1题目描述 是不是感觉好长#xff0c;我也这么觉得。哈…一.前言
今天在力扣上刷到了一道题想着和大家一起分享一下这道题——相交链表https://leetcode.cn/problems/intersection-of-two-linked-lists废话不多说让我们开始今天的分享吧。
二.正文
1.1题目描述 是不是感觉好长我也这么觉得。哈哈不过没办法大家们凑合看一下吧毕竟人家的题就那么长。
1.2题目分析
我想到有两种方法一种是暴力求解时间复杂度是ON^2还有一种是一种稍微巧妙一点的技巧时间复杂度是(N)。
两种方法共同部分
我们可以创建两个指针分别是指向headA和headB的 pcur1和pcur2。并让pcur1headA
pcur2pcurB。
我们首先需要判断该链表是不是相交链表如果是则返回相交链表的第一个相交节点。否则返回NULL。那么如何判断该链表是不是相交链表呢其实我们可以让pcur1和pcur2分别遍历两个链表的最后一个节点即可如果pcur1pcur2则说明两个链表至少有一个相交节点毫无疑问这肯定是相交节点。反之pcur1pcur2则说明不是相交链表。值得注意的是完成上面部分后记得让pcur1headApcur2headB因为pcur1和pcur2后续我们还需要重新遍历两个链表
i暴力算法
我们可以让headA中的每一个节点都与headB中的节点遍历一次然后让headA的下一个节点重复这个动作直到headA的最后一个节点遍历结束。
这是该方法的代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
ListNode* pcur1,*pcur2;
pcur1headA;
pcur2headB;
while(pcur1-next!NULL)
{pcur1pcur1-next;
}
while(pcur2-next!NULL)
{pcur2pcur2-next;
}
if(pcur2!pcur1)
return NULL;
pcur1headA;
pcur2headB;
while(pcur1-next!NULL)
{
while(pcur2-next!NULL)
{
if(pcur1pcur2)
return pcur1;
pcur2pcur2-next;
}
pcur2headB;
pcur1pcur1-next;
}
return pcur1;
}
(ii)非暴力算法 那么我们应该依据什么来遍历相对长度前的数据呢我们可以利用在遍历A和B的同时让代表A链表len1来算出长度同理len2是算出B的长度。定义一个变量gapabslen1-len2算出绝对值如果A链表长则A链表先遍历gap个长度的节点反之B链表长则B链表先遍历gap个长度的节点。
最后的步骤是上图所示相对长度中的上下节点依次比较。
三.结言
今天的题目分享就到此结束了拜拜了家人们。
