【链表】LC 160.相交链表

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析双指针解法非双指针解法哈希表2、解题代码双指针解法非双指针解法哈希表三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接160.相交链表2、题目描述二、个人思路整理1、思路分析双指针解法这个解法有点妙说实话理解不是很透彻根据自己的理解梳理一下。由于想要达到O(1)的空间复杂度不能开辟额外空间本质上还是消除两个链表的长度差由于链表在相交节点前走过的节点数是不同的所以不能直接同时遍历来找相交的节点从而达到一次遍历找到交点当然也可以先计算链表的长度差然后让长链表先走长度差距离然后再一起向后走第一个相同的节点即为交点我的理解是如果要同时一次同时遍历就能找到交点就必须把交点前的距离经过的节点数补齐补齐即可不需要管补充的这段距离是否存在相交节点如果确实存在在后续遍历中由于补充的距离不同所以不可能是在同时遍历中的第一个相同节点这样一次同时遍历当遇到的第一个相同节点即为相交节点本质上我认为是3这种理解。具体举例如果链表A长度为a、链表B长度为b相交的部分长度为c可以把从A从B链表开始遍历的距离各想成一条直线直线最后部分就是c而直线前半部分存在不相等的情况需要补全若要补全前面的长度差就可以让链表A多走一个b距离让链表B多走一个a距离这样就相当于A走了ab而B走了ba由于只是补在前面后面的共有部分没有变所以当前面走完相同距离遇到的第一个相同的点即为交点。所以最终的解法两链表同时遍历A链表先遍历一遍A若遍历完则继续遍历BB链表先遍历一遍B若遍历完则继续遍历A当遍历遇到第一个相同节点即为交点。下面为大模型给出的解释参考防遗忘为什么这个方法有效数学原理解析设链表 A 独有的长度为a aa链表 B 独有的长度为b bb两链表公共相交部分的长度为c cc那么链表 A 的总长度为a c a cac链表 B 的总长度为b c b cbc当指针 pA 走完 A 再走 B 时到达交点的总路程是a c b a c bacb当指针 pB 走完 B 再走 A 时到达交点的总路程是b c a b c abca因为a c b b c a a c b b c aacbbca所以两个指针走过的总路程完全一致这就消除掉了两条链表前段长度不一样的差值。如果不相交即c 0 c 0c0pA 走了a b a bab步后变为 nullptrpB 走了b a b aba步后也变为 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*paheadA;ListNode*pbheadB;// 当指向同一节点则结束while(pa!pb){pa(panullptr)?headB:pa-next;//当遍历完A遍历Bpb(pbnullptr)?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_setListNode*s;ListNode*tmpheadA;while(tmp!nullptr){s.insert(tmp);tmptmp-next;}tmpheadB;while(tmp!nullptr){if(s.count(tmp)){returntmp;}tmptmp-next;}returnnullptr;}};三、知识风暴NULL与nullptrC11及以上一律使用nullptr表示空指针nullptrC11 引入的关键字强类型字面量实际类型为std::nullptr_t类型的常数纯C语言或C98以前才继续使用NULLNULL宏定义通常被定义为整数0或(void*)0实际类型为整型int/long