LeetCode实战：相交链表
背景
- 为什么你要加入一个技术团队？
- 如何加入 LSGO 软件技术团队？
- 我是如何组织“算法刻意练习活动”的？
- 为什么要求团队的学生们写技术Blog
题目英文
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
begin to intersect at node c1.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
Notes:
- If the two linked lists have no intersection at all, return null.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
题目中文
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：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：
输入：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：
输入：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) 内存。
算法实现
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val = x; }* }*/public class Solution
{public ListNode GetIntersectionNode(ListNode headA, ListNode headB){HashSet<ListNode> hash = new HashSet<ListNode>();ListNode temp = headA;while (temp != null){hash.Add(temp);temp = temp.next;}temp = headB;while (temp != null){if (hash.Contains(temp))return temp;temp = temp.next;}return null;}
}
实验结果
- 状态：通过
- 45 / 45 个通过测试用例
- 执行用时: 172 ms, 在所有 C# 提交中击败了 100.00% 的用户
- 内存消耗: 37.6 MB, 在所有 C# 提交中击败了 5.88% 的用户
相关图文
1. “数组”类算法
- LeetCode实战：三数之和
- LeetCode实战：最接近的三数之和
- LeetCode实战：求众数
- LeetCode实战：缺失的第一个正数
- LeetCode实战：快乐数
- LeetCode实战：寻找两个有序数组的中位数
- LeetCode实战：盛最多水的容器
- LeetCode实战：删除排序数组中的重复项
- LeetCode实战：搜索旋转排序数组
- LeetCode实战：螺旋矩阵
- LeetCode实战：螺旋矩阵 II
2. “链表”类算法
- LeetCode实战：两数相加
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：两两交换链表中的节点
- LeetCode实战：旋转链表
- LeetCode实战：环形链表
3. “栈”类算法
- LeetCode实战：有效的括号
- LeetCode实战：最长有效括号
- LeetCode实战：逆波兰表达式求值
4. “队列”类算法
- LeetCode实战：设计循环双端队列
- LeetCode实战：滑动窗口最大值
- LeetCode实战：整数反转
- LeetCode实战：字符串转换整数 (atoi)
5. “递归”类算法
- LeetCode实战：爬楼梯
6. “位运算”类算法
- LeetCode实战：格雷编码
7. “字符串”类算法
- LeetCode实战：反转字符串
- LeetCode实战：翻转字符串里的单词
- LeetCode实战：最长公共前缀
- LeetCode实战：字符串相加
- LeetCode实战：字符串相乘
8. “树”类算法
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：二叉树的最大深度
- LeetCode实战：将有序数组转换为二叉搜索树
9. “哈希”类算法
- LeetCode实战：两数之和
10. “排序”类算法
- LeetCode实战：合并两个有序数组
- LeetCode实战：合并两个有序链表
- LeetCode实战：合并K个排序链表
11. “搜索”类算法
- LeetCode实战：搜索二维矩阵
- LeetCode实战：子集
12. “动态规划”类算法
- LeetCode实战：最长回文子串
- LeetCode实战：最大子序和
- LeetCode实战：不同路径
13. “回溯”类算法
- LeetCode实战：全排列
14. “数值分析”类算法
- LeetCode实战：回文数
- LeetCode实战：x 的平方根
相关文章：
# 30 天精通 RxJS (01)：认识 RxJS
RxJS 是笔者认为未来几年内会非常红的 Library，RxJS 提供了一套完整的非同步解决方案，让我们在面对各种非同步行为，不管是 Event, AJAX, 还是 Animation 等，我们都可以使用相同的 API (Application Programming Interface) 做开发…
ThickBox 3.1参数详解(转)
前几天写了一篇关于ThickBox 3.1的文章：今天在使用这个东西的时候发现里面有许多参数没有详细解释，今天抽空整理出来，现和大家分享一下：先说几个参数：class"thickbox" 调用特效；height 打开页面的…
最新Java培训-NIO实战教程
Java NIO(New IO)是一个可以替代标准Java IO API的IO API(从Java 1.4开始)，Java NIO提供了与标准IO不同的IO工作方式。NIO可以理解为非阻塞IO,传统的IO的read和write只能阻塞执行，线程在读写IO期间不能干其他事情，比如调用socket.read()时&am…
获取执行SQL语句的返回结果
最近遇到的问题，在存储过程中需要拼接动态SQL语句，用变量保存，可直接使用EXECUTE SP_EXECUTESQL是不能获取想要的结果的 于是经过baidu了一番后，找到了解决的办法 declare coun int,sql nvarchar(2000)setsqlselect councount(*) …
Word文档使用密码加密
Word文档使用密码加密 方法如下： 文件-->信息-->保护文档-->用密码进行加密-->设置密码
LeetCode实战：反转链表
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Ou…
【UI设计培训】字体设计-偏旁部首变形
UI设计培训中字体设计也是非常重要的一节课，字体在UI设计岗位中可以说用到的频率是非常高的，是设计师必须学会并且要有娴熟运用的一项必备技能，在进行汉字设计的时候，可以把汉字拆分成几个偏旁部首的形式进行设计，这样…
【转帖】如何通过 javascript 访问 GridView/DataGrid 选中 CheckBox 行各列的值
功能需求1, 单击 checkbox 返回当前行值2, 外部按钮获取所有选择行的值实现说明参见主要代码，代码为自说明式。原文地址：http://www.cnblogs.com/Jinglecat/archive/2007/07/15/818967.html主要代码 <asp:GridView ID"GridView1" runat&q…
LeetCode实战：删除链表中的节点
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Write a function to delete a node (except the tail) in a singly linked list, given on…
Facebook将React的许可改为MIT
Facebook决定将React原先的BSDPatents许可改为MIT，这样其他公司就可以将React包含在Apache基金会的项目当中，并消除与开源社区之间关系的不确定性。\\Facebook的一位工程主管Adam Wolff声称，将会有越来越多的项目使用MIT许可代替BSDPatents&a…
Java培训进阶书籍推荐，赶快收藏起来!
最近有很多学习或者已经在工作的java技术的同学都想要更进一步的提升自己，那么阅读书籍可以给大家带来帮助，今天，小编将分享过去几年中一些最好的Java培训进阶书籍，您可以在2021年阅读这些书籍，以更好地学习Java和相关…
LeetCode实战：二叉搜索树的最近公共祖先
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given …
[转载] 杜拉拉升职记——02 单相思与性骚扰
来源：李可. 杜拉拉升职记(第三版). 西安: 陕西师范大学出版社, 2010, 5. 02 单相思与性骚扰的区别 拉拉注意到，DB所有经理办公室沿走道的这一面，都是用大块的玻璃来做间隔墙。 拉拉问海伦：“这么设计是为了美观吗？” …
走进云计算与虚拟化的底层核心
本文讲的是走进云计算与虚拟化的底层核心,2012年3月在国务院政府工作报告附录部分中，政府对云计算给出了官方的解释，体现了政府对云计算产业的高度重视和美好愿景。云计算在工作报告中是这样定义的：“云计算是基于互联网的服务的增加、使用和…
LeetCode实战：LRU缓存机制
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Design and implement a data structure for Least Recently Used (LRU) cache. It should …
探索性测试，笔记二
测试十戒律： 1、你应该使用大量输入，来反复锤炼被测的应用程序 *大规模的随机测试（自动化），而且有助于理解输入和输出的关系 2、你应当贪图你的邻居的应用程序 3、你应当亲自寻找睿智的预言家 *对应的输入是否有对应的…
python 监控windows磁盘空间和备份大小
#!/usr/bin/env python # Version 3.5.2 # __auth__ 无名小妖 import os import time import sendmail import psutil import collectionsdisk_used collections.OrderedDict() cur_time time.time() # current_day cur_time - cur_time % 86400 root_dir ["D:\\bac…
如何高效学习java课程
想要快速进入到java行业，进行系统的培训和有效的学习是非常重要的，那么短时间内如何高效学习java课程呢?来看看下面小编的详细介绍吧。 如何高效学习java课程? 1. 克服自身惰性，学习环境更佳。 参加Java培训机构学习的话，…
2021年web前端发展方向有哪些
一年转瞬即逝，仅仅一年的时间，就能发生很多事情，近几年web前端行业越来越受到大家的关注，很多人都想看看2021年web前端发展方向有哪些?下面来看看小编详细的介绍。 2021年web前端发展方向有哪些? 1、TypeScript爆发增长 从2019年…
weblogic服务器部署的程序，如何直接通过IP访问（即URL中去掉工程名）
用weblogic部署的程序，怎么能够直接通过IP访问呢？ 下面就是了 打开你的工程，看看webroot下的WEB-INF中有没有一个weblogic.xml文件。 1、如果没有，自己建一个，里面写上： <?xml version"1.0" …
LeetCode实战：二叉搜索树中第K小的元素
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Given a binary search tree, write a function kthSmallest to find the kth smallest ele…
xml文件-1
2019独角兽企业重金招聘Python工程师标准>>> 1 Xml简单的历史介绍 1969 gml(通用标记语言) [主要的目的是要在不同的机器进行通信的数据规范] 1985 sgml(标准通用标记语言) 1993 html (www网) Html语言本身是有一些缺陷的 (1)标记不能自定义 <html> <table…
学习web前端难不难
学习web前端难不难?这是很多同学都会问到的问题，web前端在目前互联网行业的发展前景是非常可观的，想要进入到这个行业的人有很多，下面我们来看看具体的介绍。 学习web前端难不难?首先你要明白你需要什么 前发展还是后发展?定好系统的学习目…
Android对话框-下篇-之设置activity为Dialog
有人希望做出来的应用程序是一个漂浮在手机主界面的东西，那么很 简单你只需要设置一下Activity的主题就可以了在AndroidManifest.xml 中定义Activity的 地方一句话：android:theme"android:style/Theme.Dialog" 这就使你的应用程序变成对话框的…
Codeforces 846 B Math Show DFS + 贪心
题目链接： http://codeforces.com/contest/846/problem/B 题目描述： 有N个节点， 每个节点有相同的K个子节点， 每个子节点有时间花费，完成一个子节点获得1分， 每完成一个节点的所有子节点获得额外一分&…
LeetCode实战：二叉树的最近公共祖先
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the …
学习UI设计都需要了解哪些知识
由于UI设计的高薪，很多人都萌生了想要学习UI设计的想法，但是小编提醒大家，学习UI设计之前一定要做足功课，了解UI设计基本知识，再看看自己是否适合学习，下面小编就为大家详细的介绍一下学习UI设计都需要了解…
Marty Cagan：怎样寻找出色的产品经理
《程序员杂志》的文章，原帖位于http://www.programmer.com.cn/7760/ 写的很好，自己转贴存储一下，也符合Product Owner的要求，就是……要求太高了！本文是他回顾自己二十多年来从事软件产品管理工作的总结和经验分享&…
LeetCode实战：除自身以外数组的乘积
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Given an array nums of n integers where n > 1, return an array output such that ou…
PHP+MySql获取自动增长字段的新添加记录ID值
PHPMySql获取新添加记录的ID值 1.假设字段名称为recordID 2.字段属性须设为：auto_increment 3.添加数据后使用 $newID mysql_insert_id(); 得到ID值 ASP获取即时ID值 ASPAccess2000 1.要获取的ID值字段属性必须设为：自动编号(我们假设字段名为recordID)…