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

这篇具有很好参考价值的文章主要介绍了看完这篇文章你就彻底懂啦｛保姆级讲解｝-----（面试刷题链表相交） 2023.4.24。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

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

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

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

分析题目：

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

链表相交代码：

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;
    }
};

时间复杂度：O(n + m)
空间复杂度：O(1)

算法思想

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

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的长度长。
看完这篇文章你就彻底懂啦｛保姆级讲解｝-----（面试刷题链表相交） 2023.4.24

int gap = lenA - lenB;

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

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

//该操作让curA和curB在同一点上，即让链表A和链表B的末尾位置对齐
看完这篇文章你就彻底懂啦｛保姆级讲解｝-----（面试刷题链表相交） 2023.4.24

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