嵌入式软件C语言面试常见问题及答案解析（四）

嵌入式软件C语言面试常见问题及答案解析（四）
  原本打算将链表相关的面试题整合到一个文档中，奈何写着写着就发现题目比较多，题型也比较丰富，所以导致上一篇已经足够长了，再长也就有点不礼貌了。

  所以在这儿继续来总结分享那个面试中遇到的题目，文中的问题和提供的答案或者代码均代表个人的理解，如有不合理或者错误的地方，欢迎大家批评指正。

---

---

1. 把一个链表中的接点顺序逆序

题目：写出程序把一个链表中的接点顺序逆序，其中链表的结构定义如下。

typedef struct linknode
{int data;struct linknode *next;
} node;

在面试中数据结构的考题中链表的相关操作算是一个常规考题了。所以链表相关的操作最好还是熟练的好。

/* 链表逆置，输入链表头部，返回逆置之后的头部 */
node *reverse(node *head)
{/* 定义辅助指针 */node *p1 = NULL, *p2 = NULL, *p3 = NULL;/* 辅助指针定位 */p1 = head;p2 = p1->next; /* NOTE 其实就是 head->next->next *//* 循环结束的条件 */while (p2 != NULL){/* 辅助指针定位 */p3 = p2->next;/* 将当前节点的下一节点 指向 前一个节点 */p2->next = p1;/* 指针后移 */p1 = p2;p2 = p3;}/* 头节点已经变为尾节点，指向NULL */head->next = NULL;/* 重新设置输入参数为头节点 */head = p1;/* 返回新的头节点 */return head;
}

2. 单向链表删除其某一个节点的代码

题目：已知一个单向链表的头，请写出删除其某一个节点的算法，要求先找到此结点，然后删除。

题目中没有给出链表节点结构，同时也没有给出明确删除的条件（或函数原型），那么在此种情况下，可以定义两种函数原型；

1. 根据节点的数据匹配删除，函数定义为 node *linklist_delete(node *head, int key)
2. 根据节点的位置匹配删除，函数定义为 node *linklist_delete(node *head, int pos)

需要注意的是，题中相关的限定比较模糊，在设计过程中我们还需要注意几个方面：

1. 没有表明单链表是否含有头节点（标识链表头，但是无有效数据）
2. 删除位置可能是第一个节点（头节点），也可能是最后一个节点
3. 要删除的节点的生命周期管理（函数内部直接释放，或者定义函数返回值的时候将删除的节点返回出来，方便调用着对删除的节点操作（信息保存、内存释放 等等））；

下面给出参考代码（注意：本例中的头节点定义为没有有效数据的节点）。

typedef struct linknode
{int data;struct linknode *next;
} node;// 方案一
node *linklist_delete(node *head, int key)
{/* 临时辅助指针 */node *t_temp = NULL;/* 参数判断 */if (NULL != head &&NULL != head->next) /* NOTE 是否为空链表 */{/* 查找目标节点的位置 */while (head != NULL &&head->data != key){/* 保存当前节点 */t_temp = head;/* 链表节点后移 */head = head->next;}/* 是否到达尾部 */if (head != NULL){/* 删除当前节点 */t_temp->next = head->next;}}/* 返回要删除的节点 */return head;
}// 通用删除
node *linklist_delete(node *head, int pos)
{/* 临时参数定义 */node *t_temp = NULL;int i = 0;/* 参数判断 */if (NULL != head &&NULL != head->next) /* NOTE 是否为空链表 */{/* 起始位置初始化 */i = 1;/* 遍历查找目标节点 */while (i < pos && head->next != NULL){/* 循环让指针向后移动 */head = head->next;/* 位置记录 */i++;}/* 节点是否有效 */if (head->next != NULL){/* 临记录要删除的节点*/t_temp = head->next;head->next = t_temp->next; // head->next = head->next->next;}}// free(temp);  // 释放temp所代表的最后一个节点空间// temp = NULL; // 防止野指针/* 返回结果 */return t_temp;
}

3. 用于删除链表中的所有节点

题目：编写代码，用于删除链表中的所有节点。

来一个简单的题目缓缓吧

void delete_allnode(node *head)
{node *p = NULL;while (head != NULL){/* 保存下一个节点信息 */p = head->next;/* 释放当前节点 */free(head);/* 节点赋值，继续下一个节点 */head