嵌入式软件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