开封网站设计,网站建设 怎么跑业务,长沙建设教育网官网,淘宝联盟推广做网站违法目录
一、链表理论基础
二、链表相交求解思路
三、相关算法题目
四、疑点 一、链表理论基础
代码随想录
二、链表相交求解思路
链表相交时#xff0c;是结点的位置#xff0c;也就是指针相同#xff0c;不是结点的数值相同#xff1b;
思路#xff1a;定义两个指针…目录
一、链表理论基础
二、链表相交求解思路
三、相关算法题目
四、疑点 一、链表理论基础
代码随想录
二、链表相交求解思路
链表相交时是结点的位置也就是指针相同不是结点的数值相同
思路定义两个指针currA和currB分别指向链表A和链表B的头节点求出两个链表的长度lenA和lenB
如果lenBlenA交换currA和currB的指向即让currA指向链表B让currB指向链表A同时交换lenA和lenB让lenA保存较长的链表链表B的长度lenB保存链表A的长度就是currA和lenA是对应的让其表示较长的链表currB和lenB是对应的让其表示较短的链表但是不一定和headA和headB是对应的
求出两个链表的长度差gap然后让较长链表移动到 和较短链表 同长度的位置此时同时移动currA和currB 并进行比较如果不相等则依次往后移动如果相等则认为此处为链表相交的开始结点返回该位置即可否则返回null
注意⚠️求完两个链表长度后currA和currB此时指向为空应该重新初始化
三、相关算法题目
面试题目02.07. 链表相交
面试题 02.07. 链表相交 - 力扣LeetCode
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode currA headA;ListNode currB headB;int lenA 0;int lenB 0;while(currA ! null){//求链表A的长度lenA;currA currA.next;}while(currB ! null){//求链表B的长度lenB;currB currB.next;}//★容易忘记 求完长度以后 currA和currB 指向为空 需要重新赋值头节点currA headA;currB headB;if(lenB lenA){int temp lenA;lenA lenB;lenB temp;currA headB;currB headA;//就是让currA 和 lenA 指向长度更长的那个链表 headA 还是 headB 无所谓}int gap lenA - lenB;//求解两个链表长度之差while(gap ! 0){gap--;currA currA.next;//让更长的链表 移动到和较短链表同长度的位置 }while(currA ! null){if(currA currB){return currA;}currA currA.next;currB currB.next;}return null;}
}
四、疑点
1.最后相同位置判断链表A和链表B时为什么只要有一个指针相同后面的就不用判断了会不会 只有这一个相同后面的又有不同的
A不会当有一个指针的指向相同时由于链表中指针域部分只有一个指针所以之后必定也是一样的链表相交以后就不会再分开成两个不同的链表
2.法2同时移动链表的思路不太懂
3.让长链表移动到较短链表相同位置 4.本题思路
因为链表相交以后说明两个链表共享同一个链表那么相交部分的长度一定是≤ 俩链表中较短的链表所以开始相交的部分最长也就是从较短链表的头结点开始故本题思路 让长链表移动到和较短链表同长度的位置再开始比较
