赞
踩
发布:2021年8月17日10:45:05
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须保持其原始结构 。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出:Intersected at '8’ 解释:相交节点的值为 8 (注意,如果两个链表相交则不能为0)。 从各自的表头开始算起, 链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。 在 A 中,相交节点前有 2 个节点; 在 B 中,相交节点前有 3 个节点。 |
---|
示例 2:
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出:Intersected at '2’ 解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起, 链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。 在 A 中,相交节点前有 3 个节点; 在 B 中,相交节点前有 1 个节点。 |
---|
示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出:null 解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起, 链表 A 为 [2,6,4],链表 B 为 [1,5]。 由于这两个链表不相交, 所以 intersectVal 必须为 0, 而 skipA 和 skipB 可以是任意值。 这两个链表不相交,因此返回 null 。 |
---|
提示:
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点,intersectVal 为 0
如果 listA 和 listB 有交点,intersectVal == listA[skipA + 1] == listB[skipB + 1]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
因为题目中要求了==函数返回结果后,链表必须保持其原始结构 。==所以,我们就不能像之前做【判断链表中是否有环状结构】(详见下方参考)中那样给节点添加某个标记了,否则的话就可以直接先遍历一遍其中一个链表,并给该链表的每一个节点添加一个访问标志;然后再遍历另一个链表并检查节点中是否有访问标志,一旦发现访问标志则说明该节点是链表的交点,立即将其返回即可。但是很可惜,题目中有了不能修改原链表的限制,所以只能想其他办法了。
思路比较直接,就是用两层嵌套的while
循环来分别遍历两个链表,我选择外层循环用来遍历链表headA
,内层循环遍历headB
(这里的先后顺序无所谓,你也可以选择外B内A)。终止条件就是用于遍历headA
的指针p
所指向的链表元素与用于遍历headB
的指针q
所指向的链表元素是同一个元素时返回p
指针所指向的元素。如果外层循环都遍历完了还没有找到符合题意的元素则返回null
。详解请看下方注释。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { // 初始化指针p指向headA首元节点,初始化指针q指向headB首元节点 let p = headA; let q = headB; // 如果headA或者headB为空链表,直接返回null if(!headA || !headB) { return null; } // 如果p指针还没遍历至headA末尾,则在内层while循环中开始进行对headB的重头遍历 // 当遍历至链表末尾时,指针的值为null,转化为布尔值就是false while(p) { while(q) { // 如果两个指针指向的元素是同一个,说明当前节点就是两个链表的交叉点,直接将其返回 if(q === p) { return p; } // 否则继续判断q的下一个元素是不是和p指向同一个元素 q = q.next; } // 如果当前的p指针指向的元素不是交叉点,则继续判断该元素的下一个元素 p = p.next; // 一定要将q指针的指向重新调回headB的头部 q = headB; } // headA都被遍历完了还没找到符合要求的节点就返回null return null; }; 提交记录 39 / 39 个通过测试用例 状态:通过 执行用时:852 ms, 在所有 JavaScript 提交中击败了5.02%的用户 内存消耗:44.2 MB, 在所有 JavaScript 提交中击败了83.74%的用户 时间:2021/08/17 11:11
可以看到,上面的程序的时间表现非常地差,如果两个链表的长度分别为m
和n
的话,其时间复杂度应该就是O(mxn)
。
上面的解法还是性能还是不够好,我记得之前做过一个获取链表中倒数第k个节点的题目:
这里就用到了双指针的思想,我就想能不能在这道题中也用上双指针呢?但是headA
和headB
两个链表的长度并不一致,如何判断交点呢?上面那个链表题中有一个让其中一个指针先走的骚操作,然后再让两个指针同步运动。我的目的就是让两个指针能够同步运动,现在唯一的阻碍就是链表长度不一致的问题。
也就是说必须想办法让p
和q
指针指向的元素到交点的距离是一样的时候再让两个指针同步运动。即:抹除长度差。
既然如此,那大可以借鉴上面那个链表题中的做法,让长度较长的那个链表上的指针先走若干步,使得两个指针到各自链表末尾的距离一样即可。也就是我下面封装的辅助函数synchronizeLength
所做的事。
在写这个函数时我碰上一个坑,那就是你将
ListNode
对象传入之后,预期中应该是对该传入的对象作出修改,我们不用再操心其他事了。但事实是,我们应该将修改的结果作为返回值返回,否则就只是在synchronizeLength()
函数的作用域内对形参head
做了修改,我们传入的那个ListNode
对象作为实参并没有如预期中那样被修改。所以最后一定要将操作后的结果作为返回值返回!!!
同步了长度之后就好办了,直接让两个指针开始同步运动,然后判断两个指针指向的元素是不是同一个,如果是的话就直接将其作为结果返回。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { // 如果其中一个链表为空,那么直接返回null if(!headA || !headB) { return null; } // lengthDiff用于存储两个链表的长度之差,注意这里得到的结果可能是负数 // 这里不做取绝对值的操作是因为下面还需要用到它做判断 let lengthDiff = getListLength(headA) - getListLength(headB); let p = headA; let q = headB; // lengthDiff > 0 ? p = synchronizeLength(p, lengthDiff) : q = synchronizeLength(q, lengthDiff); // 如果headA链表长度大于headB,则让headA先走几步以抹除长度差;反之则让headB先走几步 // 这个if-else逻辑和上面注释掉的三元运算是等效的,但是我觉得这个更清晰一点 if (lengthDiff > 0) { p = synchronizeLength(p, lengthDiff); } else { q = synchronizeLength(q, lengthDiff); } // 在抹除长度差后,开始让两个指针同步往后运动,直到两个指针指向同一个节点 // 如果指针已经到达末尾仍未发现交点则返回null while(p !== q) { if(!p) { return null; } p = p.next; q = q.next; } return p; // 该函数用于获取head到链表末尾的距离,当head是首元节点时, // 其返回结果即为一个链表的长度,head是一个ListNode类型的数据 function getListLength(head) { let length = 0; while(head) { length++; head = head.next; } return length; } // 该函数用于让较长的链表上的指针先走若干步,使得两个指针到链表末尾的距离一样 // head是ListNode类型的数据,diff是两个链表的长度之差,千万记得要将结果返回!! function synchronizeLength(head, diff) { // 传进来的diff有可能是负数,这时我们要取它的绝对值 let absoluteDiff = Math.abs(diff); while(absoluteDiff > 0) { head = head.next; absoluteDiff--; } return head; } }; 提交记录 39 / 39 个通过测试用例 状态:通过 执行用时:80 ms, 在所有 JavaScript 提交中击败了97.36%的用户 内存消耗:44.8 MB, 在所有 JavaScript 提交中击败了31.78%的用户 时间:2021/08/17 15:01
可以看到,上面的程序的时间变现明显比第一种解法更好。没有了双层while
循环,那么时间复杂度应该是O(n)
。
在链表类题目中,双指针的思想往往非常有用,它能够为链表的遍历做一些标记,毕竟单链表是不支持往前访问的。
更新:2021年7月29日18:43:21
因为我考虑到著作权归属问题,所以【官方题解】部分我不再粘贴具体的代码了,可到下方的链接中查看。
更新:2021年8月17日11:14:01
【更新结束】
更新:2021年8月17日11:23:26
参考:【算法-剑指 Offer】22. 链表中倒数第k个节点_赖念安的博客-CSDN博客
参考:【算法-LeetCode】141. 环形链表_赖念安的博客-CSDN博客
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。