【链表】LC 160.相交链表

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

160.相交链表

2、题目描述

二、个人思路整理

1、思路分析

双指针解法

这个解法有点妙，说实话理解不是很透彻，根据自己的理解梳理一下。

1. 由于想要达到O(1)的空间复杂度，不能开辟额外空间；
2. 本质上还是消除两个链表的长度差（由于链表在相交节点前走过的节点数是不同的，所以不能直接同时遍历来找相交的节点），从而达到一次遍历找到交点（当然也可以先计算链表的长度差，然后让长链表先走长度差距离，然后再一起向后走，第一个相同的节点即为交点）；
3. 我的理解是：如果要同时一次同时遍历就能找到交点，就必须把交点前的距离（经过的节点数补齐（补齐即可，不需要管补充的这段距离是否存在相交节点，如果确实存在，在后续遍历中由于补充的距离不同，所以不可能是在同时遍历中的第一个相同节点），这样一次同时遍历，当遇到的第一个相同节点即为相交节点）；
4. 本质上我认为是3这种理解。具体举例：

• 如果链表A长度为a、链表B长度为b，相交的部分长度为c（可以把从A从B链表开始遍历的距离各想成一条直线，直线最后部分就是c，而直线前半部分存在不相等的情况需要补全）
• 若要补全前面的长度差，就可以让链表A多走一个b距离，让链表B多走一个a距离，这样就相当于A走了a+b，而B走了b+a，由于只是补在前面，后面的共有部分没有变，所以当前面走完相同距离遇到的第一个相同的点即为交点。

5. 所以，最终的解法：
   两链表同时遍历：
   A链表先遍历一遍A，若遍历完则继续遍历B；
   B链表先遍历一遍B，若遍历完则继续遍历A；
   当遍历遇到第一个相同节点即为交点。

下面为大模型给出的解释（参考防遗忘）

为什么这个方法有效？（数学原理解析）设：

• 链表 A 独有的长度为a aa
• 链表 B 独有的长度为b bb
• 两链表公共（相交）部分的长度为c cc
  那么：
• 链表 A 的总长度为a + c a + ca+c
• 链表 B 的总长度为b + c b + cb+c

当指针 pA 走完 A 再走 B 时，到达交点的总路程是：a + c + b a + c + ba+c+b
当指针 pB 走完 B 再走 A 时，到达交点的总路程是：b + c + a b + c + ab+c+a
因为a + c + b = b + c + a a + c + b = b + c + aa+c+b=b+c+a，所以两个指针走过的总路程完全一致！这就消除掉了两条链表前段长度不一样的差值。

• 如果不相交（即c = 0 c = 0c=0）：pA 走了a + b a + ba+b步后变为 nullptr，pB 走了b + a b + ab+a步后也变为 nullptr，此时 pA == pB == nullptr，完美统一了逻辑。

非双指针解法（哈希表）

遍历链表A，将元素放置到哈希表中，然后从头节点开始依次遍历链表B，遍历到第一个的存在于哈希表中的节点，即为相交节点，否则不相交。

2、解题代码

双指针解法

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){ListNode*pa=headA;ListNode*pb=headB;// 当指向同一节点则结束while(pa!=pb){pa=(pa==nullptr)?headB:pa->next;//当遍历完A遍历Bpb=(pb==nullptr)?headA:pb->next;//当遍历完B遍历A}returnpa;}};

非双指针解法（哈希表）

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){unordered_set<ListNode*>s;ListNode*tmp=headA;while(tmp!=nullptr){s.insert(tmp);tmp=tmp->next;}tmp=headB;while(tmp!=nullptr){if(s.count(tmp)){returntmp;}tmp=tmp->next;}returnnullptr;}};

三、知识风暴

• NULL与nullptr
  • C++11及以上一律使用nullptr表示空指针（nullptr：C++11 引入的关键字，强类型字面量；实际类型为std::nullptr_t类型的常数）；
  • 纯C语言或C++98以前才继续使用NULL（NULL：宏定义，通常被定义为整数0或(void*)0；实际类型为整型（int/long））