网站推广怎么做 知乎,怎样做网站的优化排名,做网站公司分为国内还是国外,网站开发教学视频教程题目分析#xff1a;
. - 力扣#xff08;LeetCode#xff09; 相交链表#xff1a;首先我想到的第一个思路是#xff1a;如图可知#xff0c;A和B链表存在长度差#xff0c;从左边一起遍历链表不好找交点#xff0c;那我们就从后面开始找#xff0c;但是这是单链表
. - 力扣LeetCode 相交链表首先我想到的第一个思路是如图可知A和B链表存在长度差从左边一起遍历链表不好找交点那我们就从后面开始找但是这是单链表没有 prev 指针所以只能反转链表 A、B。反转之后再从A、B头结点开始就可以找到相遇点但是题目要求我们不能改变链表的结构所以此方法不行。 方法一 思路 ①当链表有一个为空或者两个都为空的时候直接返回NULL。 ②因为链表存在差值结点个数不同不能一起遍历所以我们可以求出A和B各自的结点个数然后求出差值。 ③差值有了之后我们可以让长的链表先走差值步相对于抹掉了差值。 ④最后A、B链表一起走如果地址相等就表示相遇了就返回交点处的地址如果没有相遇就返回NULL struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {struct ListNode* curA headA;struct ListNode* curB headB;if (curA NULL || curB NULL)return NULL;//求链表A、B各自的长度int la 0;int lb 0;while (curA) {curA curA-next;la;}while (curB) {curB curB-next;lb;}//找到两个链表中较长的那个struct ListNode* longest headA;struct ListNode* shortest headB;if (la lb) {longest headB;shortest headA;}//求出差值然后先让长的链表走完差值int gap abs(la - lb);while (gap--) {longest longest-next;}//同时出发直到相遇否则没有相遇while (longest) {if (longest shortest)return longest;longest longest-next;shortest shortest-next;}return NULL;
} 方法二 思路 ①当链表有一个为空或者两个都为空的时候直接返回NULL。 ②相当于两个指针在一个路线上走、走的路程都是一样的 A先走完自己的路程然后去走B的路程 B先走完自己的路程然后去走A的路程 A和B走到路一样长 如果存在相遇点A和B必定会相遇 (如果不是很明白可以对着代码画图去理解一下) 如果不存在相遇点就在NULL处相遇 struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {if (headANULL || headBNULL){return NULL;}struct ListNode* A headA;struct ListNode* B headB;while (A ! B) {A A ? A-next : headB; B B ? B-next : headA;}return A;
}
