力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
第五章 - 高频考题(中等)
面试题 17.09. 第 k 个数
面试题 17.23. 最大黑方阵
面试题 16.16. 部分排序
Increasing Digits
Longest Contiguously Strictly Increasing Sublist After Deletion
Consecutive Wins
Number of Substrings with Single Character Difference
Bus Fare
Minimum Dropping Path Sum
Every Sublist Min Sum
Maximize the Number of Equivalent Pairs After Swaps
0002. 两数相加
0003. 无重复字符的最长子串
0005. 最长回文子串
0011. 盛最多水的容器
0015. 三数之和
0017. 电话号码的字母组合
0019. 删除链表的倒数第 N 个节点
0022. 括号生成
0024. 两两交换链表中的节点
0029. 两数相除
0031. 下一个排列
0033. 搜索旋转排序数组
0039. 组合总和
0040. 组合总和 II
0046. 全排列
0047. 全排列 II
0048. 旋转图像
0049. 字母异位词分组
0050. Pow(x, n)
0055. 跳跃游戏
0056. 合并区间
0060. 第 k 个排列
0061. 旋转链表
0062. 不同路径
0073. 矩阵置零
0075. 颜色分类
0078. 子集
0079. 单词搜索
0080. 删除排序数组中的重复项 II
0086. 分隔链表
0090. 子集 II
0091. 解码方法
0092. 反转链表 II
0094. 二叉树的中序遍历
0095. 不同的二叉搜索树 II
0096. 不同的二叉搜索树
0098. 验证二叉搜索树
0102. 二叉树的层序遍历
0103. 二叉树的锯齿形层次遍历
0113. 路径总和 II
0129. 求根到叶子节点数字之和
0130. 被围绕的区域
0131. 分割回文串
0139. 单词拆分
0144. 二叉树的前序遍历
0147. 对链表进行插入排序
0150. 逆波兰表达式求值
0152. 乘积最大子数组
0153. 寻找旋转排序数组中的最小值
0199. 二叉树的右视图
0200. 岛屿数量
0201. 数字范围按位与
0208. 实现 Trie (前缀树)
0209. 长度最小的子数组
0211. 添加与搜索单词 - 数据结构设计
0215. 数组中的第 K 个最大元素
0220. 存在重复元素 III
0221. 最大正方形
0227. 基本计算器 II
0229. 求众数 II
0230. 二叉搜索树中第 K 小的元素
0236. 二叉树的最近公共祖先
0238. 除自身以外数组的乘积
0240. 搜索二维矩阵 II
0279. 完全平方数
0309. 最佳买卖股票时机含冷冻期
0322. 零钱兑换
0328. 奇偶链表
0331. 验证二叉树的前序序列化
0334. 递增的三元子序列
0337. 打家劫舍 III
0343. 整数拆分
0365. 水壶问题
0378. 有序矩阵中第 K 小的元素
0380. 常数时间插入、删除和获取随机元素
0394. 字符串解码
0416. 分割等和子集
0424. 替换后的最长重复字符
0438. 找到字符串中所有字母异位词
0445. 两数相加 II
0454. 四数相加 II
0456. 132 模式
0457.457. 环形数组是否存在循环
0464. 我能赢么
0470. 用 Rand7() 实现 Rand10
0473. 火柴拼正方形
0494. 目标和
0516. 最长回文子序列
0513. 找树左下角的值
0518. 零钱兑换 II
0525. 连续数组
0547. 朋友圈
0560. 和为 K 的子数组
0609. 在系统中查找重复文件
0611. 有效三角形的个数
0673. 最长递增子序列的个数
0686. 重复叠加字符串匹配
0714. 买卖股票的最佳时机含手续费
0718. 最长重复子数组
0735. 行星碰撞
0754. 到达终点数字
0785. 判断二分图
0790. 多米诺和托米诺平铺
0799. 香槟塔
0801. 使序列递增的最小交换次数
0816. 模糊坐标
0820. 单词的压缩编码
0838. 推多米诺
0873. 最长的斐波那契子序列的长度
0875. 爱吃香蕉的珂珂
0877. 石子游戏
0886. 可能的二分法
0898. 子数组按位或操作
0900. RLE 迭代器
0911. 在线选举
0912. 排序数组
0932. 漂亮数组
0935. 骑士拨号器
0947. 移除最多的同行或同列石头
0959. 由斜杠划分区域
0978. 最长湍流子数组
0987. 二叉树的垂序遍历
1004. 最大连续 1 的个数 III
1011. 在 D 天内送达包裹的能力
1014. 最佳观光组合
1015. 可被 K 整除的最小整数
1019. 链表中的下一个更大节点
1020. 飞地的数量
1023. 驼峰式匹配
1031. 两个非重叠子数组的最大和
1043. 分隔数组以得到最大和
1104. 二叉树寻路
1129. 颜色交替的最短路径
1131.绝对值表达式的最大值
1138. 字母板上的路径
1186. 删除一次得到子数组最大和
1218. 最长定差子序列
1227. 飞机座位分配概率
1261. 在受污染的二叉树中查找元素
1262. 可被三整除的最大和
1297. 子串的最大出现次数
1310. 子数组异或查询
1334. 阈值距离内邻居最少的城市
1371.每个元音包含偶数次的最长子字符串
1381. 设计一个支持增量操作的栈
1438. 绝对差不超过限制的最长连续子数组
1558. 得到目标数组的最少函数调用次数
1574. 删除最短的子数组使剩余数组有序
1631. 最小体力消耗路径
1658. 将 x 减到 0 的最小操作数
1697. 检查边长度限制的路径是否存在
1737. 满足三条件之一需改变的最少字符数
1834. 单线程 CPU
1899. 合并若干三元组以形成目标三元组
1904. 你完成的完整对局数
1906. 查询差绝对值的最小值
1906. 查询差绝对值的最小值
2007. 从双倍数组中还原原数组
2008. 出租车的最大盈利
5935. 适合打劫银行的日子
5936. 引爆最多的炸弹
5965. 相同元素的间隔之和
第六章 - 高频考题(困难)
后序
由
GitBook
提供支持
0061. 旋转链表
题目地址(61. 旋转链表)
https://leetcode-cn.com/problems/rotate-list/
题目描述
1
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
2
3
示例 1:
4
5
输入: 1->2->3->4->5->NULL, k = 2
6
输出: 4->5->1->2->3->NULL
7
解释:
8
向右旋转 1 步: 5->1->2->3->4->NULL
9
向右旋转 2 步: 4->5->1->2->3->NULL
10
示例 2:
11
12
输入: 0->1->2->NULL, k = 4
13
输出: 2->0->1->NULL
14
解释:
15
向右旋转 1 步: 2->0->1->NULL
16
向右旋转 2 步: 1->2->0->NULL
17
向右旋转 3 步: 0->1->2->NULL
18
向右旋转 4 步: 2->0->1->NULL
Copied!
快慢指针法
前置知识
求单链表的倒数第 N 个节点
思路一
1.
采用快慢指
2.
快指针与慢指针都以每步一个节点的速度向后遍历
3.
快指针比慢指针先走 N 步
4.
当快指针到达终点时,慢指针正好是倒数第 N 个节点
思路一代码
伪代码
1
快指针
=
head
;
2
慢指针
=
head
;
3
while
(
快指针
.
next
)
{
4
if
(
N
--
<=
0
)
{
5
慢指针
=
慢指针
.
next
;
6
}
7
快指针
=
快指针
.
next
;
8
}
Copied!
语言支持: JS
JS Code:
1
let
slow
=
(
fast
=
head
);
2
while
(
fast
.
next
)
{
3
if
(
k
--
<=
0
)
{
4
slow
=
slow
.
next
;
5
}
6
fast
=
fast
.
next
;
7
}
Copied!
思路二
1.
获取单链表的倒数第 N + 1 与倒数第 N 个节点
2.
将倒数第 N + 1 个节点的 next 指向 null
3.
将链表尾节点的 next 指向 head
4.
返回倒数第 N 个节点
例如链表 A -> B -> C -> D -> E 右移 2 位,依照上述步骤为:
1.
获取节点 C 与 D
2.
A -> B -> C -> null, D -> E
3.
D -> E -> A -> B -> C -> nul
4.
返回节点 D
注意:假如链表节点长度为 len, 则右移 K 位与右移动 k % len 的效果是一样的 就像是长度为 1000 米的环形跑道, 你跑 1100 米与跑 100 米到达的是同一个地点
思路二代码
伪代码
1
获取链表的长度
2
k
=
k
%
链表的长度
3
获取倒数第k
+
1
,
倒数第
K
个节点与链表尾节点
4
倒数第k
+
1
个节点
.
next
=
null
5
链表尾节点
.
next
=
head
6
return
倒数第k个节点
Copied!
语言支持: JS, JAVA, Python, CPP, Go, PHP
JS Code:
1
var
rotateRight
=
function
(
head
,
k
)
{
2
if
(
!
head
||
!
head
.
next
)
return
head
;
3
let
count
=
0
,
4
now
=
head
;
5
while
(
now
)
{
6
now
=
now
.
next
;
7
count
++
;
8
}
9
k
=
k
%
count
;
10
let
slow
=
(
fast
=
head
);
11
while
(
fast
.
next
)
{
12
if
(
k
--
<=
0
)
{
13
slow
=
slow
.
next
;
14
}
15
fast
=
fast
.
next
;
16
}
17
fast
.
next
=
head
;
18
let
res
=
slow
.
next
;
19
slow
.
next
=
null
;
20
return
res
;
21
};
Copied!
JAVA Code:
1
class
Solution
{
2
public
ListNode
rotateRight
(
ListNode
head
,
int
k
)
{
3
if
(
head
==
null
||
head
.
next
==
null
)
return
head
;
4
int
count
=
0
;
5
ListNode
now
=
head
;
6
while
(
now
!=
null
){
7
now
=
now
.
next
;
8
count
++
;
9
}
10
k
=
k
%
count
;
11
ListNode
slow
=
head
,
fast
=
head
;
12
while
(
fast
.
next
!=
null
){
13
if
(
k
--
<=
0
){
14
slow
=
slow
.
next
;
15
}
16
fast
=
fast
.
next
;
17
}
18
fast
.
next
=
head
;
19
ListNode
res
=
slow
.
next
;
20
slow
.
next
=
null
;
21
return
res
;
22
}
23
}
Copied!
Python Code:
1
class
Solution
:
2
def
rotateRight
(
self
,
head
:
ListNode
,
k
:
int
)
->
ListNode
:
3
# 双指针
4
if
head
:
5
p1
=
head
6
p2
=
head
7
count
=
1
8
i
=
0
9
while
i
<
k
:
10
if
p2
.
next
:
11
count
+=
1
12
p2
=
p2
.
next
13
else
:
14
k
=
k
%
count
15
i
=
-
1
16
p2
=
head
17
i
+=
1
18
19
while
p2
.
next
:
20
p1
=
p1
.
next
21
p2
=
p2
.
next
22
23
if
p1
.
next
:
24
tmp
=
p1
.
next
25
else
:
26
return
head
27
p1
.
next
=
None
28
p2
.
next
=
head
29
return
tmp
Copied!
CPP Code:
1
class
Solution
{
2
int
getLength
(
ListNode
*
head
)
{
3
int
len
=
0
;
4
for
(;
head
;
head
=
head
->
next
,
++
len
);
5
return
len
;
6
}
7
public
:
8
ListNode
*
rotateRight
(
ListNode
*
head
,
int
k
)
{
9
if
(
!
head
)
return
NULL
;
10
int
len
=
getLength
(
head
);
11
k
%=
len
;
12
if
(
k
==
0
)
return
head
;
13
auto
p
=
head
,
q
=
head
;
14
while
(
k
--
)
q
=
q
->
next
;
15
while
(
q
->
next
)
{
16
p
=
p
->
next
;
17
q
=
q
->
next
;
18
}
19
auto
h
=
p
->
next
;
20
q
->
next
=
head
;
21
p
->
next
=
NULL
;
22
return
h
;
23
}
24
};
Copied!
Go Code:
1
/**
2
* Definition for singly-linked list.
3
* type ListNode struct {
4
* Val int
5
* Next *ListNode
6
* }
7
*/
8
func
rotateRight
(
head
*
ListNode
,
k
int
)
*
ListNode
{
9
if
head
==
nil
||
head
.
Next
==
nil
{
10
return
head
11
}
12
n
:=
0
13
p
:=
head
14
for
p
!=
nil
{
15
n
++
16
p
=
p
.
Next
17
}
18
k
=
k
%
n
19
// p 为快指针, q 为慢指针
20
p
=
head
21
q
:=
head
22
for
p
.
Next
!=
nil
{
23
p
=
p
.
Next
24
if
k
>
0
{
25
k
--
26
}
else
{
27
q
=
q
.
Next
28
}
29
}
30
// 更新指针
31
p
.
Next
=
head
32
head
=
q
.
Next
33
q
.
Next
=
nil
34
35
return
head
36
}
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
/**
13
*
@param
ListNode
$head
14
*
@param
Integer
$k
15
*
@return
ListNode
16
*/
17
function
rotateRight
(
$head
,
$k
)
18
{
19
if
(
!
$head
||
!
$head
->
next
)
return
$head
;
20
21
$p
=
$head
;
22
$n
=
0
;
23
while
(
$p
)
{
24
$n
++
;
25
$p
=
$p
->
next
;
26
}
27
$k
=
$k
%
$n
;
28
$p
=
$q
=
$head
;
// $p 快指针; $q 慢指针
29
while
(
$p
->
next
)
{
30
$p
=
$p
->
next
;
31
if
(
$k
>
0
)
$k
--
;
32
else
$q
=
$q
->
next
;
33
}
34
$p
->
next
=
$head
;
35
$head
=
$q
->
next
;
36
$q
->
next
=
null
;
37
38
return
$head
;
39
}
40
}
Copied!
复杂度分析
时间复杂度:节点最多只遍历两遍,时间复杂度为$O(N)$
空间复杂度:未使用额外的空间,空间复杂度$O(1)$
以前
0060. 第 k 个排列
下一个
0062. 不同路径
最近更新
1yr ago
复制链接
内容
题目地址(61. 旋转链表)
题目描述
快慢指针法
前置知识
思路一
思路一代码
思路二
思路二代码