力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
面试题 17.12. BiNode
0001. 两数之和
0020. 有效的括号
0021. 合并两个有序链表
0026. 删除排序数组中的重复项
0053. 最大子序和
0160. 相交链表
0066. 加一
0088. 合并两个有序数组
0101. 对称二叉树
0104. 二叉树的最大深度
0108. 将有序数组转换为二叉搜索树
0121. 买卖股票的最佳时机
0122. 买卖股票的最佳时机 II
0125. 验证回文串
0136. 只出现一次的数字
0155. 最小栈
0167. 两数之和 II 输入有序数组
0169. 多数元素
0172. 阶乘后的零
0190. 颠倒二进制位
0191. 位 1 的个数
0198. 打家劫舍
0203. 移除链表元素
0206. 反转链表
0219. 存在重复元素 II
0226. 翻转二叉树
0232. 用栈实现队列
0263. 丑数
0283. 移动零
0342. 4 的幂
0349. 两个数组的交集
0371. 两整数之和
401. 二进制手表
0437. 路径总和 III
0455. 分发饼干
0504. 七进制数
0575. 分糖果
0665. 非递减数列
0661. 图片平滑器
821. 字符的最短距离
0874. 模拟行走机器人
1128. 等价多米诺骨牌对的数量
1260. 二维网格迁移
1332. 删除回文子序列
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
0160. 相交链表
题目地址(160. 相交链表)
https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
题目描述
1
编写一个程序,找到两个单链表相交的起始节点。
Copied!
前置知识
链表
双指针
解法一: 哈希法
有 A, B 这两条链表, 先遍历其中一个,比如 A 链表, 并将 A 中的所有节点存入哈希表。
遍历 B 链表,检查节点是否在哈希表中, 第一个存在的就是相交节点
伪代码
1
data
=
new
Set
()
// 存放A链表的所有节点的地址
2
3
while
A
不为空
{
4
哈希表中添加
A
链表当前节点
5
A
指针向后移动
6
}
7
8
while
B
不为空
{
9
if
如果哈希表中含有
B
链表当前节点
10
return
B
11
B
指针向后移动
12
}
13
14
return
null
// 两条链表没有相交点
Copied!
代码支持: JS
JS Code:
1
let
data
=
new
Set
();
2
while
(
A
!==
null
)
{
3
data
.
add
(
A
);
4
A
=
A
.
next
;
5
}
6
while
(
B
!==
null
)
{
7
if
(
data
.
has
(
B
))
return
B
;
8
B
=
B
.
next
;
9
}
10
return
null
;
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(N)$
解法二:双指针
例如使用 a, b 两个指针分别指向 A, B 这两条链表, 两个指针相同的速度向后移动,
当 a 到达链表的尾部时,重定位到链表 B 的头结点
当 b 到达链表的尾部时,重定位到链表 A 的头结点。
a, b 指针相遇的点为相交的起始节点,否则没有相交点
(图 5)
为什么 a, b 指针相遇的点一定是相交的起始节点? 我们证明一下:
1.
将两条链表按相交的起始节点继续截断,链表 1 为: A + C,链表 2 为: B + C
2.
当 a 指针将链表 1 遍历完后,重定位到链表 B 的头结点,然后继续遍历直至相交点(a 指针遍历的距离为 A + C + B)
3.
同理 b 指针遍历的距离为 B + C + A
4.
伪代码
1
a
=
headA
2
b
=
headB
3
while
a
,
b指针不相等时
{
4
if
a指针为空时
5
a指针重定位到链表
B
的头结点
6
else
7
a指针向后移动一位
8
if
b指针为空时
9
b指针重定位到链表
A
的头结点
10
else
11
b指针向后移动一位
12
}
13
return
a
Copied!
代码支持: JS, Python, Go, PHP
JS Code:
1
var
getIntersectionNode
=
function
(
headA
,
headB
)
{
2
let
a
=
headA
,
3
b
=
headB
;
4
while
(
a
!=
b
)
{
5
a
=
a
===
null
?
headB
:
a
.
next
;
6
b
=
b
===
null
?
headA
:
b
.
next
;
7
}
8
return
a
;
9
};
Copied!
Python Code:
1
class
Solution
:
2
def
getIntersectionNode
(
self
,
headA
:
ListNode
,
headB
:
ListNode
)
->
ListNode
:
3
a
,
b
=
headA
,
headB
4
while
a
!=
b
:
5
a
=
a
.
next
if
a
else
headB
6
b
=
b
.
next
if
b
else
headA
7
return
a
Copied!
Go Code:
1
/**
2
* Definition for singly-linked list.
3
* type ListNode struct {
4
* Val int
5
* Next *ListNode
6
* }
7
*/
8
func
getIntersectionNode
(
headA
,
headB
*
ListNode
)
*
ListNode
{
9
// a=A(a单独部分)+C(a相交部分); b=B(b单独部分)+C(b相交部分)
10
// a+b=b+a=A+C+B+C=B+C+A+C
11
a
:=
headA
12
b
:=
headB
13
for
a
!=
b
{
14
if
a
==
nil
{
15
a
=
headB
16
}
else
{
17
a
=
a
.
Next
18
}
19
if
b
==
nil
{
20
b
=
headA
21
}
else
{
22
b
=
b
.
Next
23
}
24
}
25
return
a
26
}
Copied!
PHP Code:
1
/**
2
* Definition for a singly-linked list.
3
* class ListNode {
4
* public $val = 0;
5
* public $next = null;
6
* function __construct($val) { $this->val = $val; }
7
* }
8
*/
9
class
Solution
10
{
11
/**
12
* @param ListNode $headA
13
* @param ListNode $headB
14
* @return ListNode
15
*/
16
function
getIntersectionNode
(
$headA
,
$headB
)
17
{
18
$a
=
$headA
;
19
$b
=
$headB
;
20
while
(
$a
!==
$b
)
{
// 注意, 这里要用 !==
21
$a
=
$a
?
$a
->
next
:
$headB
;
22
$b
=
$b
?
$b
->
next
:
$headA
;
23
}
24
return
$a
;
25
}
26
}
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(1)$
以前
0053. 最大子序和
下一个
0066. 加一
最近更新
1yr ago
复制链接
内容
题目地址(160. 相交链表)
题目描述
前置知识
解法一: 哈希法
解法二:双指针