当前位置：首页 > article >正文

代码随想录刷题day14(2)|（链表篇）02.07. 链表相交（疑点）

article 2025/1/27 4:02:32

一、链表理论基础

二、链表相交求解思路

三、相关算法题目

四、疑点

一、链表理论基础

代码随想录

二、链表相交求解思路

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

思路：定义两个指针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;
    }
}