1. 首页

LeetCode 160. 相交链表

题目描述

难度:Easy

相关话题:链表

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表

LeetCode 160. 相交链表

在节点 c1 开始相交。

示例 1:

LeetCode 160. 相交链表

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例2:

LeetCode 160. 相交链表

输入:intersectVal= 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例3:

LeetCode 160. 相交链表

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。

注意:

  • 如果两个链表没有交点,返回 null .

  • 在返回结果后,两个链表仍须保持原有的结构。

  • 可假定整个链表结构中没有循环。

  • 程序尽量满足 O(n ) 时间复杂度,且仅用 O(1 ) 内存。


思路:

假设nodeheadA遍历完后接着从headB开始,nodeBheadB到遍历完后接着从headA开始,那么最后这两条链表是等长的,并且最终他们会同时到达
headA==null && headB==null的状态。

而在这段遍历中,如果存在nodeA===nodeB的情况,说明这就是它们的相交点。

否则则不存在相交点。

/**
 * @ Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * 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) {
  if(!headA || !headB)return null
  let nodeA=headA,nodeB=headB
  while(nodeA || nodeB){
    if(!nodeA)nodeA=headB
    if(!nodeB)nodeB=headA
    if(nodeA===nodeB)return nodeA
    nodeA=nodeA.next
    nodeB=nodeB.next
  }
  return null
};

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 160. 相交链表

链接:https://www.javascriptc.com/4521.html

« 移动端适配及PC端适配心得总结体会(二) (可能比较全
【必收藏】前端优化详解以及需要关注的几个问题»
Flutter 中文教程资源

相关推荐

QR code