不用服务器做网站线上编程课程

目录

一、链表理论基础

二、链表相交求解思路

三、相关算法题目

四、疑点

---

一、链表理论基础

代码随想录

二、链表相交求解思路

链表相交时，是结点的位置，也就是指针相同，不是结点的数值相同；

思路：定义两个指针currA和currB，分别指向链表A和链表B的头节点，求出两个链表的长度lenA和lenB；

如果lenB＞lenA，交换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.本题思路

因为链表相交以后，说明两个链表共享同一个链表，那么相交部分的长度一定是≤ 俩链表中较短的链表，所以开始相交的部分最长也就是从较短链表的头结点开始，故本题思路 让长链表移动到和较短链表同长度的位置再开始比较；