免费网站建设可信赖,西部数码里面如何建设自己的网站,惠州做网站哪家公司好,百度推广怎么联系原题链接#xff1a;https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
看到这道题#xff0c;很容易想到的方法就是暴力求解#xff0c;就是将一个链表的每个结点的地址…原题链接https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
目录
1. 题目描述
2. 思路分析
3. 代码实现 1. 题目描述 2. 思路分析
看到这道题很容易想到的方法就是暴力求解就是将一个链表的每个结点的地址分别和另外一个链表的每个结点的地址进行比较如果有相等的就说明相交了。注意这里不能比值因为两个不同的结点值有可能一样。但是这样的时间复杂度太高了为O(N^2)。
这道题有一个很好的做法
先计算出两个链表的长度让长的链表先走相差的长度然后两个链表同时走直到遇到相同的结点即为第一个公共结点。
我们定义了四个变量curAcurBlenAlenB。
我们用结构体指针curA遍历链表A用结构体指针curB遍历链表B。
lenA表示链表A的长度lenB表示链表B的长度。
用while循环通过遍历分别得到了链表A和B的长度。
我们判断尾结点是否相等如果尾结点相等说明两个链表一定相交
我们看下图如果两个链表相交那么从这个相交的结点包括这个交点之后的结点在两个链表中都是相等的。所以尾结点相等说明两个链表一定相交。 如果两个链表不相交curA!curB我们直接返回空指针NULL。
如果两个链表相交我们先让长的链表走两个链表长度的差距步gap。因为不知道两个链表哪个长所以我们使用了abs()函数差距步gap就是abs(lenA-lenB。
之后我们又引入了两个结构体指针longList和shortList分别指向长链表和短链表的头。这里用了if语句判断先假设某个链表是长链表如果不是就让它等于短链表。
然后我们用一个while循环让长链表走差距步while(gap--)。 然后让longList和shortList这两个结构体指针同时走找交点找到交点时结束循环。
最后返回longList即可。 3. 代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curAheadA,*curBheadB;int lenA1,lenB1;//计算链表长度while(curA-next){curAcurA-next; lenA;}while(curB-next){curBcurB-next;lenB;}//不相交if(curA!curB)return NULL;int gapabs(lenA-lenB);struct ListNode *longListheadA,*shortListheadB;if(lenAlenB){longListheadB;shortListheadA;}//长的先走差距步while(gap--){longListlongList-next;}//同时走找交点while(longList!shortList){longListlongList-next;shortListshortList-next;}return longList;
}
