1. 算法刷题实战：从链表到树的系统突破
最近五个月，我系统性地刷完了力扣面试热题101榜单中的链表、树、队列/栈等核心数据结构题目，完成了第四轮地毯式轰炸。作为嵌入式开发背景的工程师，我特别注重用C语言实现这些算法，因为在实际嵌入式系统开发中，对数据结构的掌握程度直接决定了代码效率和质量。
刷题过程中，我采用了"三遍法则"：第一遍理解思路，第二遍优化代码，第三遍提炼模板。现在分享的这些代码都是经过至少3-4次迭代的最终版本，包含了从新手到进阶的完整思考过程。特别适合准备技术面试的同行参考，尤其是那些需要同时应对算法考察和嵌入式开发的岗位。
2. 链表操作：从基础到高阶的完整实现
2.1 链表反转的三种境界
链表反转是面试最高频的题目之一，我经历了从初级到优化的完整迭代过程。最初版本容易忽略头节点为空的边界条件：
c复制struct ListNode* ReverseList(struct ListNode* head) {
if(head == NULL) return NULL; // 关键边界检查
struct ListNode *pre = NULL;
struct ListNode *p = head;
struct ListNode *pNext = head;
while(p != NULL) {
pNext = p->next; // 先保存下一个节点
p->next = pre; // 反转指针方向
pre = p; // 移动pre指针
p = pNext; // 移动当前指针
}
return pre; // 新头节点
}
进阶版本需要考虑部分反转的场景，这是实际工作中更常见的情况。比如反转链表中m到n位置的节点：
c复制struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
if(head == NULL || m > n) return NULL;
if(m == n) return head;
// 定位m位置的前驱节点和n位置的后继节点
struct ListNode *pmpre = (m == 1) ? NULL : head;
struct ListNode *pm = (m == 1) ? head : head->next;
for(int i=0; i<m-2 && pmpre!=NULL; i++) {
pmpre = pmpre->next;
pm = pm->next;
}
struct ListNode *pn = head;
for(int i=0; i<n-1 && pn!=NULL; i++) {
pn = pn->next;
}
struct ListNode *pnnext = pn->next;
// 执行局部反转
struct ListNode *pre = pmpre;
struct ListNode *cur = pm;
while(cur != pnnext) {
struct ListNode *next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
// 重新连接链表
if(pmpre != NULL) {
pmpre->next = pre;
} else {
head = pre; // 处理m=1的特殊情况
}
pm->next = pnnext;
return head;
}
注意事项：部分反转时要特别注意m=1的边界情况，此时头节点会发生变化。在实际嵌入式开发中，这类指针操作要格外小心内存访问越界问题。
2.2 链表合并与排序实战
合并两个有序链表是基础但重要的操作，在嵌入式系统的消息队列处理中经常用到：
c复制struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2) {
if(pHead1 == NULL) return pHead2;
if(pHead2 == NULL) return pHead1;
struct ListNode dummy = {0, NULL};
struct ListNode *p = &dummy;
while(pHead1 != NULL && pHead2 != NULL) {
if(pHead1->val < pHead2->val) {
p->next = pHead1;
pHead1 = pHead1->next;
} else {
p->next = pHead2;
pHead2 = pHead2->next;
}
p = p->next;
}
p->next = (pHead1 != NULL) ? pHead1 : pHead2;
return dummy.next;
}
对于更复杂的链表排序，归并排序是最佳选择，时间复杂度O(nlogn)：
c复制struct ListNode* sortInList(struct ListNode* head) {
if(head == NULL || head->next == NULL) return head;
// 快慢指针找中点
struct ListNode *slow = head;
struct ListNode *fast = head->next;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
// 分割链表
struct ListNode *mid = slow->next;
slow->next = NULL;
// 递归排序
struct ListNode *left = sortInList(head);
struct ListNode *right = sortInList(mid);
// 合并有序链表
return merge(left, right);
}
实操心得：在嵌入式环境下，递归深度可能受栈空间限制，对于超长链表建议使用非递归实现。在资源受限的MCU上，我通常会限制链表的最大长度。
3. 链表高级应用与问题排查
3.1 环检测与数学原理
检测链表是否有环是经典问题，快慢指针法是最优解：
c复制bool hasCycle(struct ListNode *head) {
if(head == NULL || head->next == NULL) return false;
struct ListNode *slow = head;
struct ListNode *fast = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) return true;
}
return false;
}
这个算法背后的数学原理很有意思：如果存在环，快指针最终会从后面追上慢指针，就像两个人在环形跑道上跑步，速度快的最终会套圈速度慢的。
3.2 链表倒数第K个节点
嵌入式开发中经常需要处理类似场景，比如查找日志链表的最后几条记录：
c复制struct ListNode* FindKthToTail(struct ListNode* pHead, int k) {
if(pHead == NULL || k <= 0) return NULL;
struct ListNode *fast = pHead;
struct ListNode *slow = pHead;
// 快指针先走k-1步
for(int i=0; i<k-1; i++) {
if(fast->next == NULL) return NULL; // k大于链表长度
fast = fast->next;
}
// 同步移动直到快指针到达末尾
while(fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
3.3 链表公共节点与内存管理
查找两个链表的第一个公共节点，这在嵌入式系统的内存池管理中很常见：
c复制struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2) {
if(pHead1 == NULL || pHead2 == NULL) return NULL;
struct ListNode *p1 = pHead1;
struct ListNode *p2 = pHead2;
while(p1 != p2) {
p1 = (p1 == NULL) ? pHead2 : p1->next;
p2 = (p2 == NULL) ? pHead1 : p2->next;
}
return p1;
}
内存管理提示：在嵌入式C编程中，链表节点通常从固定内存池分配，而不是直接使用malloc/free，这样可以避免内存碎片问题。我在实际项目中会预分配节点数组，通过指针链接实现链表。
4. 大数加法与链表应用
嵌入式系统有时需要处理大数运算，用链表存储数字各位是常见方案：
c复制struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2) {
if(head1 == NULL) return head2;
if(head2 == NULL) return head1;
// 反转链表以便从低位开始相加
head1 = reverse(head1);
head2 = reverse(head2);
struct ListNode dummy = {0, NULL};
struct ListNode *p = &dummy;
int carry = 0;
while(head1 != NULL || head2 != NULL || carry != 0) {
int val1 = (head1 != NULL) ? head1->val : 0;
int val2 = (head2 != NULL) ? head2->val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = sum % 10;
node->next = NULL;
p->next = node;
p = p->next;
if(head1 != NULL) head1 = head1->next;
if(head2 != NULL) head2 = head2->next;
}
// 再次反转得到正确顺序的结果
return reverse(dummy.next);
}
性能优化：在资源受限的嵌入式设备上，可以预先计算两个链表的长度，只为结果链表分配一次内存，而不是每个节点单独分配。此外，如果不需要保留原始链表，可以直接在原链表上操作节省内存。
5. 刷题方法论与嵌入式实践
5.1 我的四轮刷题策略
- 第一轮：理解基础思路，实现基础功能
- 第二轮：优化代码结构，处理边界条件
- 第三轮：提炼算法模板，形成肌肉记忆
- 第四轮：模拟面试场景，提升白板编码能力
在嵌入式开发中，我特别注重以下几点：
- 内存使用效率：尽可能使用原地算法
- 时间复杂度：避免在中断处理中使用高复杂度算法
- 可读性：良好的代码注释和模块划分
5.2 常见问题排查记录
-
指针越界问题：
- 症状：程序随机崩溃
- 解决方法：在访问指针前总是检查NULL，特别是在嵌入式系统没有MMU保护的情况下
-
内存泄漏：
- 症状：系统运行时间越长，可用内存越少
- 解决方法：使用静态内存池替代动态分配，或者确保每个malloc都有对应的free
-
递归深度过大：
- 症状：栈溢出导致系统崩溃
- 解决方法：对于可能的大数据量，改用迭代算法
5.3 嵌入式开发中的实用技巧
-
使用位域优化链表节点的存储：
c复制struct ListNode { int val; unsigned int is_allocated:1; // 标记位 struct ListNode* next; }; -
在RTOS环境中，对共享链表的操作需要加锁：
c复制void addNode(struct ListNode** head, int val) { rtos_mutex_lock(&list_mutex); // 安全的链表操作 rtos_mutex_unlock(&list_mutex); } -
使用内存池管理链表节点：
c复制#define POOL_SIZE 100 static struct ListNode node_pool[POOL_SIZE]; static int pool_index = 0; struct ListNode* alloc_node(int val) { if(pool_index >= POOL_SIZE) return NULL; node_pool[pool_index].val = val; node_pool[pool_index].next = NULL; return &node_pool[pool_index++]; }
经过这五个月的系统训练，我对链表相关算法题已经形成了条件反射般的熟悉度。在最近的面试中，无论面试官如何变化题目要求，我都能快速识别出问题的本质并给出优化方案。这种能力不是一蹴而就的，而是通过反复练习和总结获得的。