🧮 Algorithm Notebook
1、算法准备
1.1 牛客网编程OJ的典型输入输出
2、算法框架
2.1 动态规划
2.1.1 斐波那契数列
2.1.2 背包问题
2.1.3 贪心算法
2.1.4 序列和数组类问题
2.1.5 编辑距离
2.1.6 高楼扔鸡蛋
2.1.7 股票问题系列通解
2.1.8 最长有效括号
2.1.9 剪绳子
2.1.10 正则表达式匹配
2.2 二分查找
2.2.1 二分查找框架
2.2.2 搜索旋转排序数组
2.3 链表
2.3.1 反转链表
2.3.2 相交链表
2.3.3 合并链表
2.3.4 链表中倒数第k个节点
2.3.5 复制带随机指针的链表
2.4 排序算法
2.4.1 常见排序算法
2.5 二叉树
2.5.1 二叉树遍历
2.5.2 岛屿问题
2.5.3 二叉树路径问题
2.5.4 构造二叉树
2.6 回溯算法
2.6.1 回溯算法解题框架
2.6.2 N皇后
2.7 数组
2.7.1 删除有序数组中的重复项
2.7.2 滑动窗口最大值
2.7.3 调整数组顺序使奇数位于偶数前面
2.7.4 螺旋矩阵
2.7.5 多数元素
2.7.6 最大数
2.7.7 和为s的两个数字
2.7.8 构建乘积数组
2.7.9 两数之和
2.8 字符串
2.8.1 最小覆盖子串
2.8.2 比较版本号
2.8.3 验证IP地址
2.8.4 基本计算器 II
2.8.5 字符串解码
2.8.6 移掉 K 位数字
2.8.7 无重复字符的最长子串
2.8.8 第一个只出现一次的字符
2.8.9 翻转字符串里的单词
2.8.10 字符串转换整数 (atoi)
2.8.11 字符串四则运算
2.9 栈
2.9.1 最小栈
2.9.2 弹出序列
2.10 数学
2.10.1 用 Rand7() 实现 Rand10()
2.10.2 只出现一次的数字
2.10.3 整数反转
2.10.4 求1+2+…+n
2.10.5 二进制中1的个数
2.10.6 幂运算
2.10.7 1~n 整数中 1 出现的次数
2.10.8 数字序列中某一位的数字
2.10.9 丑数
2.10.10 n个骰子的点数
2.10.11 圆圈中最后剩下的数字
2.10.12 不用加减乘除做加法
2.10.13 x 的平方根
2.11 设计
2.11.1 LRU 缓存机制
-
+
游客
注册
登录
相交链表
## 题目 编写一个程序,找到两个单链表相交的起始节点。 如下面的两个链表: ![](https://notebook.ricear.com/media/202105/2021-05-24_203625.png) 在节点 c1 开始相交。 **示例 1:** ![](https://notebook.ricear.com/media/202105/2021-05-24_203718.png) ```txt 输入: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:** ![](https://notebook.ricear.com/media/202105/2021-05-24_203739.png) ```txt 输入: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:** ![](https://notebook.ricear.com/media/202105/2021-05-24_203755.png) ```txt 输入: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) 内存。 ## 解题思路 ### HashMap #### 问题解析 1. 将一个链表中的所有节点信息存入到**HashMap**中: * **key**:当前节点的地址 * **Value**:当前节点的父节点(头结点的父节点为**null**) 2. 然后依次遍历另一个链表: 1. 如果**HashMap**中包含当前节点的**key**,同时其对应的**value**不等于当前节点的父节点,则当前节点即为两个链表相交的起始节点。 2. 如果遍历到最后不存在的话,则直接返回**null**。 ![](https://notebook.ricear.com/media/202105/2021-05-24_211658.png) #### 参考代码 ```java /** * 160. 相交链表 * @param headA 第一个链表的头结点 * @param headB 第二个链表的头结点 * @return */ public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 解决 headA 和 headB 相同的情况 if (headA == headB) {return headA;} Map<ListNode, ListNode> map = new HashMap<>(); ListNode p = headA, prev = null; while (p != null) { map.put(p, prev); prev = p; p = p.next; } p = headB; prev = null; while (p != null) { if (map.containsKey(p) && map.get(p) != prev) {return p;} prev = p; p = p.next; } return null; } ``` ### 双指针 > 两个指针最后 **一定会相等**。 #### 问题解析 1. 开始时令指针**head1=headA**,**head2=headB**。 2. 然后两个指针分别从两个链表的起点开始遍历: 1. 当其中一个指针到达链表的尾部时,则令其等于**另一个链表**的**头部**,然后继续开始遍历,例如**head1**遍历到**headA**的尾部时,令**head1=headB**。 3. 在两次遍历的过程中,因为两个指针最终走的路程一样,所以: 1. 如果两个链表相交时,两个指针一定会在两个链表相交的节点相遇。 2. 如果两个链表不相交时,最后两个指针一定会在链表的尾部相遇,即两个指针最后的值都为**null**。 ![](https://notebook.ricear.com/media/202105/2021-05-24_204857.png) 将二者的路径拼接到一起进行展示: ![](https://notebook.ricear.com/media/202105/160-相交链表(解法二:双指针)(展示方法二)_1621860793.gif) #### 参考代码 ```java /** * 160. 相交链表 * @param headA 第一个链表的头结点 * @param headB 第二个链表的头结点 * @return */ public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 如果 headA 或 headB 为 null,则两个链表肯定不相交,直接返回 null if (headA == null || headB == null) {return null;} ListNode head1 = headA, head2 = headB; // 两次遍历: // 如果两个链表有交点,则最后 head1 一定为二者的交点 // 如果两个链表没有交点,则一定是在最后到尾节点的时候二者相遇,此时 head1 为 null while (head1 != head2) { if (head1 == null) { // 如果 head1 走到了尾节点,则令其等于 headB 的头结点 head1 = headB; } else { // 否则的话,继续遍历即可 head1 = head1.next; } if (head2 == null) { // 如果 head2 走到了尾节点,则令其等于 headA 的头结点 head2 = headA; } else { // 否则的话,继续遍历即可 head2 = head2.next; } } return head1; } ``` ## 参考文献 1. [160. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists)。 2. [图解相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t)。
ricear
2022年7月17日 10:39
©
BY-NC-ND(4.0)
转发文档
收藏文档
上一篇
下一篇
手机扫码
复制链接
手机扫一扫转发分享
复制链接
Markdown文件
分享
链接
类型
密码
更新密码