（嵌入式八股）第9章 嵌入式常考手撕题(二)：大厂相关！

大厂题目成百上千，哪些才是嵌入式面试常考的呢，本篇文章就总结了嵌入式面试中常考的大厂相关的手撕题目，关注收藏不迷路！

9.17 单向链表（Singly Linked List）

什么是单向链表？

单向链表（Singly Linked List）是一种 链式存储结构，每个节点包含：

• 数据域（val）：存储节点的数据。
• 指针域（next）：指向下一个节点的指针。

单向链表的特点

✅ 动态存储分配，不需要预先分配固定大小的数组。

✅ 插入、删除操作 O(1)，比数组更高效。

✅ 占用更少的内存（比双向链表少一个 prev 指针）。

✅ 不支持反向遍历，只能从头遍历到尾。

完整代码

代码解析

1. ListNode 结构

• 作用：链表的基本单元。
• 组成：

数据域 (val)：存储数据。

指针域 (next)：指向下一个节点。

2. create_node 函数

• 作用：动态创建新节点。
• 关键步骤：

分配内存 (malloc)。

初始化 val，next 设为 NULL（表示新节点为尾节点）。

3. insert_at_head 函数

• 作用：在链表头部插入新节点。
• 核心思想：

新节点的 next 指向当前 head。

更新 head 指向新节点。

• 时间复杂度：O(1)。

4. insert_at_tail 函数

• 作用：在链表尾部插入新节点。
• 核心思想：

遍历链表找到尾节点。

让尾节点的 next 指向新节点。

• 时间复杂度：O(n)。

5. delete_node 函数

• 作用：删除指定值的节点。
• 核心思想：

找到目标节点，调整前一节点的 next 指针，使其跳过目标节点。

释放目标节点的内存。

• 特殊情况：如果要删除的是头节点，需要特殊处理，直接更新 head。

6. traverse_list 函数

• 作用：遍历并打印链表内容。
• 实现：
• 从头遍历链表，逐个打印 val，直到 NULL。

7. free_list 函数

• 作用：释放链表占用的内存。
• 重要性：防止 内存泄漏。
• 实现：
• 逐个释放节点，直到链表为空。

9.18 双向链表（Doubly Linked List）

什么是双向链表？

双向链表是一种 链式存储结构，每个节点包含：

1. 数据域（如：int val）。
2. 指向下一个节点的指针 next。
3. 指向上一个节点的指针 prev。

双向链表的特点

✅ 支持双向遍历（可以从头遍历到尾，也可以从尾遍历到头）。

✅ 插入和删除操作为 O(1)（不需要像数组那样移动大量元素）。

✅ 比单向链表占用更多内存（因为每个节点存储两个指针）。

完整代码

代码解析

1. ListNode 结构

在双向链表的基础上，我们添加了 int val 作为数据域，使得每个节点可以存储一个整数值：

val 用于存储数据，其他部分与普通双向链表相同。

next 指向下一个节点，prev 指向前一个节点。

2. rt_list_init()—— 初始化链表

• 让 next 和 prev 指向自己，表示当前链表为空。

3. create_node()—— 创建新节点

申请新节点的内存，初始化 val 值。

通过 rt_list_init() 让 next 和 prev 指向自己。

4. rt_list_insert_after()—— 在指定节点后插入

n 的 next 设为 l->next，即 n 连接 l 的后继。

l->next->prev 设为 n，让原后继的 prev 指向 n。

l->next 设为 n，n->prev 设为 l。

5. rt_list_insert_before()—— 在指定节点前插入

n 的 prev 设为 l->prev，next 设为 l。

l->prev->next 设为 n，l->prev 设为 n。

6. rt_list_remove()—— 删除节点

让 n->prev->next 指向 n->next，n->next->prev 指向 n->prev，即把 n 从链表中断开。

n->next = n->prev = n; 避免悬空指针。

7. traverse_forward() 和 traverse_backward()—— 遍历链表

• 从 head->next 开始遍历，直到回到 head，打印 val 值。

• 从 head->prev 开始遍历，直到回到 head。

9.19 反转单向链表（Reverse Linked List）

1. 题目解析

目标：原地反转链表，使 head->next->...->NULL 变成 NULL<-...<-head。

要求：

不使用额外空间，即 O(1) 空间复杂度。

时间复杂度 O(n)，遍历链表一次即可完成。

2. 关键思路

采用三指针法（prev、cur、temp）

prev 指针：指向 当前节点的前一个节点（初始 nullptr）。

cur 指针：当前遍历的节点（初始 head）。

temp 指针：存储 cur->next，防止 next 丢失。

核心逻辑

遍历整个链表：

temp = cur->next 先存储下一个节点。

cur->next = prev 反转 cur 指向 prev。

移动 prev 和 cur 指针：

prev = cur，cur = temp。

遍历结束，prev 即为新链表头。

3. 代码实现

4. 代码解析

（1）定义链表结构

数据域 (val)：存储节点值。

指针域 (next)：指向下一个节点。

构造函数：初始化 val 并将 next 设为 nullptr。

（2）三指针法反转链表

存储 cur->next，防止 next 丢失。

反转 cur->next 指向 prev，实现翻转。

移动 prev 和 cur 指针，继续处理下一个节点。

prev 成为新的链表头。

（3）遍历并打印链表

• 从 head 开始遍历，输出 val 值直到 nullptr。

5. 复杂度分析

• 时间复杂度：O(n)（遍历一次链表）。
• 空间复杂度：O(1)（只使用三个指针 prev、cur、temp）。

9.20 二分查找（Binary Search）

二分查找基本思想

二分查找是一种高效的搜索算法，适用于 有序数组。它的基本思想是：

确定搜索范围：设定 left = 0（左边界）和 right = len - 1（右边界）。

计算中间索引：mid = (left + right) / 2。

比较目标值：

如果 a[mid] == num，找到目标，返回索引 mid。

如果 a[mid] < num，说明目标值在 mid 右侧，调整 left = mid + 1 继续搜索。

如果 a[mid] > num，说明目标值在 mid 左侧，调整 right = mid - 1 继续搜索。

循环执行：直到 left > right，表示搜索范围为空，则返回 -1（未找到）。

二分查找完整代码

函数 binary_search

• 传入 有序数组a[]，数组长度 len，以及要查找的数 num。
• 初始化 left = 0，right = len - 1。
• 通过 mid = left + (right - left) / 2 计算中点索引，避免整数溢出。
• 循环执行：
• a[mid] == num 返回索引 mid。
• a[mid] < num 向右侧搜索（left = mid + 1）。
• a[mid] > num 向左侧搜索（right = mid - 1）。
• 直到 left > right 仍未找到，则返回 -1。

main 函数

• 定义有序数组 {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}。
• 计算数组长度 len。
• 查找目标值 7，调用 binary_search。
• 根据返回值输出 索引 或 未找到 信息。

复杂度分析

• 时间复杂度：O(log n)，每次搜索范围减半，效率远高于线性查找 O(n)。
• 空间复杂度：O(1)，只使用常数级别的变量（left、right、mid）。

适用场景

• 适用于 有序数组，在无序数据中不可用。
• 在大规模数据中搜索速度极快，例如：
• 数据库索引查找
• 搜索引擎关键词查找
• 排序后的列表搜索（如电话号码查找）

9.21 滑动窗口（Sliding Window）

滑动窗口思想

1.寻找最长子数组

适用情况：

✅ 数组或字符串问题（如 无重复字符的最长子串）。

✅ 当窗口条件满足时，扩大右边界，直到不满足，再收缩左边界。

步骤：

初始化 左右指针 L = 0, R = 0，维护窗口内容。

右指针 R 向右滑动，扩大窗口，使其尽可能满足条件。

一旦不满足条件，左指针 L 右移，直到窗口重新满足条件。

重复步骤 2-3，直到 R 到达数组结尾，窗口滑动完成。

2. 寻找最短子数组

适用情况：✅ 数组或字符串问题（如 最小长度的子数组和 ≥ 目标值）。

✅ 先右移 R 扩大窗口，再左移 L 尽可能缩小窗口。

步骤：

初始化 左右指针 L = 0, R = 0，维护 sum 记录窗口和。

右指针 R 向右滑动，扩大窗口，直到 sum ≥ target。

窗口满足条件时，移动左指针 L缩小窗口，寻找更短的解。

重复步骤 2-3，直到 R 到达数组结尾，窗口滑动完成。

最短子数组和 ≥ 目标值

窗口扩展：sum += nums[right] → R 向右滑动，累加和。

窗口收缩：while(sum >= target) → L 右移，寻找更短的解。

保证 best 记录最优解（best = right - left + 1）。

返回 best，若未找到子数组，返回 0。

nums = [2,3,1,2,4,3]，目标 target = 7最短子数组 [4,3]（长度 2）的和 4+3 = 7 满足条件。

无重复字符的最长子串

窗口扩展：right++ 右移，并记录 lastSeen[current]。

窗口收缩：如果 current 已在窗口内，移动 left。

保证 maxLength 记录最优解。

str = "abcabcbb"，最长无重复子串 abc 长度 3。

复杂度分析