看完这篇文章你就彻底懂啦｛保姆级讲解｝-----（面试刷题链表相交） 2023.4.24

目录

• • 前言
  • 面试题（链表相交）—（保姆级别讲解）
  • 结束语

前言

本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可，撰写本文章主要目的在于记录自己学习体会并分享给大家，全篇并不仅仅是复制粘贴，更多的是加入了自己的思考，希望读完此篇文章能真正帮助到您！！！

面试题（链表相交）—（保姆级别讲解）

分析题目：

1. 两个链表都是单链表
2. 目标是找到并且返回两个单链表的相交的起始节点（假设现在有两个单链表分别是A和B，我们先不管A和B这两个单链表的长度谁长谁短，我们需要将A和B的尾节点对齐）
3. 整个链式结构不存在环

链表相交代码：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { 
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { 
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
       
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        
        int gap = lenA - lenB;
       
        while (gap--) {
            curA = curA->next;
        }
        
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

算法思想

好！按照老样子，接下来开始详细讲解每行代码的用处，以及为什么这样写！

ListNode* curA = headA;
ListNode* curB = headB;

//设置两个指针curA和curB分别指向链表A和链表B的头节点。

int lenA = 0, lenB = 0;

//设置链表A和链表B的长度，并初始化为0

while (curA != NULL) { 
            lenA++;
            curA = curA->next;
        }

while (curB != NULL) { 
            lenB++;
            curB = curB->next;
        }

//计算链表A和链表B的节点数量，也就是计算链表长度。

curA = headA;
curB = headB;

//设置两个指针curA和curB分别指向链表A和链表B的头节点。

if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }

//因为有三种情况，分别是lenB > lenA或者lenB < lenA或者lenB = lenA，当lenB = lenA时自然不需要处理。所以我们为了统一操作标准，不管链表A的长度长还是链表B的长度长，都设置为链表A的长度比链表B的长度长。

int gap = lenA - lenB;

//计算链表A和链表B的长度差

while (gap--) {
            curA = curA->next;
        }

//该操作让curA和curB在同一点上，即让链表A和链表B的末尾位置对齐

while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
return NULL;

//遍历链表A和链表B（分别从curA和curB开始），如果发现相同，则代表成功找到交点。如果不相同，则同时向后移动curA和curB。否则循环退出返回空指针

结束语

如果觉得这篇文章还不错的话，记得点赞 ，支持下！！！