登录遍历链表（Python/Java/C++/C/Go/JS/Rust）
如何遍历一个链表？代码框架如下：
# 遍历链表 head
while head: # 从链表头节点开始向后遍历，直到遇到空节点
print(head.val) # 当前节点值
head = head.next # 准备遍历下一个节点
// 遍历链表 head
while (head != null) { // 从链表头节点开始向后遍历，直到遇到空节点
System.out.println(head.val); // 当前节点值
head = head.next; // 准备遍历下一个节点
}
// 遍历链表 head
while (head) { // 从链表头节点开始向后遍历，直到遇到空节点
cout << head->val << endl; // 当前节点值
head = head->next; // 准备遍历下一个节点
}
// 遍历链表 head
while (head) { // 从链表头节点开始向后遍历，直到遇到空节点
printf("%d\n", head->val); // 当前节点值
head = head->next; // 准备遍历下一个节点
}
// 遍历链表 head
for head != nil { // 从链表头节点开始向后遍历，直到遇到空节点
fmt.Println(head.Val) // 当前节点值
head = head.Next // 准备遍历下一个节点
}
// 遍历链表 head
while (head) { // 从链表头节点开始向后遍历，直到遇到空节点
console.log(head.val); // 当前节点值
head = head.next; // 准备遍历下一个节点
}
// 遍历链表 head
let mut cur = &head; // 这样写，下面 let Some(node) = cur 不会转移 head 中节点的所有权
while let Some(node) = cur { // 从链表头节点开始向后遍历，直到遇到空节点
println!("{}", node.val); // 当前节点值
cur = &node.next; // 准备遍历下一个节点
}
问题相当于给你一串 $0$ 和 $1$，把它们拼成一个二进制数。
从我们熟悉的十进制开始。类比把字符串（字符数组）转成十进制整数的方式，比如 $[1,2,3]$ 转成 $123$：
- 初始化答案为 $0$。
- $0\times 10 + 1 = 1$。
- $1\times 10 + 2 = 12$。
- $12\times 10 + 3 = 123$。
本题是二进制，比如 $1,1,0$，目标是得到二进制数 $110_{(2)}$。
- 初始化答案为 $0$。
- $0_{(2)} \times 2 + 1 = 1_{(2)}$。
- $1_{(2)} \times 2 + 1 = 11_{(2)}$。乘 $2$ 等价于左移 $1$。
- $11_{(2)}\times 2 + 0 = 110_{(2)}$。
class Solution:
def getDecimalValue(self, head: Optional[ListNode]) -> int:
ans = 0
while head:
ans = ans * 2 + head.val
head = head.next
return ans
class Solution {
public int getDecimalValue(ListNode head) {
int ans = 0;
while (head != null) {
ans = ans * 2 + head.val;
head = head.next;
}
return ans;
}
}
class Solution {
public:
int getDecimalValue(ListNode* head) {
int ans = 0;
while (head) {
ans = ans * 2 + head->val;
head = head->next;
}
return ans;
}
};
int getDecimalValue(struct ListNode* head) {
int ans = 0;
while (head) {
ans = ans * 2 + head->val;
head = head->next;
}
return ans;
}
func getDecimalValue(head *ListNode) (ans int) {
for head != nil {
ans = ans*2 + head.Val
head = head.Next
}
return
}
var getDecimalValue = function(head) {
let ans = 0;
while (head !== null) {
ans = ans * 2 + head.val;
head = head.next;
}
return ans;
};
impl Solution {
pub fn get_decimal_value(head: Option<Box<ListNode>>) -> i32 {
let mut ans = 0;
let mut cur = &head;
while let Some(node) = cur {
ans = ans * 2 + node.val;
cur = &node.next;
}
ans
}
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是链表的长度。
- 空间复杂度：$\mathcal{O}(1)$。
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
