嗨，这里是逻辑iOS技术号：一个让知识变得感性，让学习变得轻松！活跃的技术小站，希望给你的生活与技术带来意思不一样！关注公众号，回复“      面试题  ”，即可领取更多大厂面试题型哦~ 小逻辑相信我们的生活不止眼前的苟且，还有我们向往的诗和大厂高薪工作~

定义结构体

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int *///定义结点typedef struct Node{    ElemType data;    struct Node *next;}Node;typedef struct Node * LinkList;

（滑动显示更多）

尾插法创建链表

前面讲过，链表的尾插法创建，新节点放在尾节点之后，但是循环链表要注意新尾节点的next指向：

完整函数片段

/* 1、链表是否已经存在 2、若不存在，创建新节点，头指针指向新节点，新节点->next指向新节点 3、若已存在，尾插法向后新增节点，新的尾节点->next指向首元节点，即*L */Status CreateList(LinkList *L){    int item;    LinkList temp = NULL; // 每次创建的新节点    LinkList fp = NULL; // 标记尾节点    while (1) {        scanf("%d",&item); // 输入创建的新值        if (item == 0) break;  // 输入为0时，结束创建        if (*L == NULL)        {            // 创建首元节点            temp = (LinkList)malloc(sizeof(Node));            if (temp == NULL) return 0;            temp->data = item; // 向节点写入数据            temp->next = temp; // 首元节点的next指向自己，因为只有自己一个节点            fp = temp;  // 首元节点也是尾节点            *L = temp;  // 头指针指向首元节点        }        else        {            // 向链表后追加新节点，并更新尾节点            // 创建新节点            temp = (LinkList)malloc(sizeof(Node));            if (temp == NULL) return 0;            temp->data = item;            // 新节点next指向尾节点的next   因为是循环，尾节点的next其实就是*L,            // temp->next = fp->next;            temp->next = *L;            // 尾节点指向新节点            fp->next = temp;            // 更新尾节点            fp = temp;        }    }    return 1;}int main(int argc, const char * argv[]) {    LinkList head;    // 创建    CreateList(&head);    // 输出链表    PrintList(head);    return 0;}

（滑动显示更多）

输出结果

遍历

void PrintList(LinkList L){    if (L == NULL)    {        printf("链表为空！");    }    else    {        /*         第一种遍历方式         *///        LinkList temp = L;//        do{//            printf("%5d",temp->data);//            temp = temp->next;//        }while (temp != L);        /*         第二种遍历方式        *///        LinkList temp = L;//        while (temp->next != L) {//            printf("%5d",temp->data);//            temp = temp->next;//        }//        printf("%5d\n",temp->data);        /*         第三种遍历方式        */        LinkList temp = L;        for (; temp->next!=L; temp = temp->next) {            printf("%5d",temp->data);        }        printf("%5d\n",temp->data);    }}

（滑动显示更多）

插入

注意：  插入数据是需要判断是不是插入在首节点位置 why?

插入位置在首元节点

temp = (LinkList)malloc(sizeof(Node));if (temp == NULL) return ERROR;temp->data = m;// 1、找到尾节点targetfor (target = *L; target->next != *L; target = target->next) ;// 2、新节点指向首节点temp->next = *L;// 3、尾节点指向新节点target->next = temp;// 4、头指针指向新首元节点*L = temp;

插入在其他任意位置

int i; // 辅助确定插入位置temp = (LinkList)malloc(sizeof(Node));if (temp == NULL) return ERROR;temp->data = m;// 1、找到插入位置的前一个节点targetfor (i = 1, target = *L; target->next != *L && i != index-1; i++,target = target->next) ;// 2、新节点 指向 target的后节点temp->next = target->next;// 3、target 指向 新节点target->next = temp;

完整函数片段

/// 插入数据/// @param L 链表（链表的头指针）/// @param index 插入位置 1是首元节点 所以插入位置要从1开始/// @param m 插入的节点数据Status ListInsert(LinkList *L, int index, int m){    LinkList target = NULL; // 插入的节点的前一个节点    LinkList temp = NULL;   // 新节点    if (index < 1) return ERROR;    if (index == 1)    {        temp = (LinkList)malloc(sizeof(Node));        if (temp == NULL) return ERROR;        temp->data = m;        // 1、找到尾节点target        for (target = *L; target->next != *L; target = target->next) ;        // 2、新节点指向首节点        temp->next = *L;        // 3、尾节点指向新节点        target->next = temp;        // 4、头指针指向新首元节点        *L = temp;    }    else    {        int i; // 辅助确定插入位置        temp = (LinkList)malloc(sizeof(Node));        if (temp == NULL) return ERROR;        temp->data = m;        // 1、找到插入位置的前一个节点target        for (i = 1, target = *L; target->next != *L && i != index-1; i++,target = target->next) ;        // 2、新节点 指向 target的后节点        temp->next = target->next;        // 3、target 指向 新节点        target->next = temp;    }    return OK;}

删除

删除首元节点

// 1、找到尾节点targetfor (target = *L; target->next != *L; target = target->next);temp = *L; // temp要删除的节点// 2、尾节点指向删除节点后的节点target->next = (*L)->next;// 3、首指针指向尾节点后的节点*L = target->next;// 4、释放free(temp);

删除其他任意节点

int i;// 1、找到尾节点target  和 要删除的tempfor (i=1, target = *L; target->next != *L && i < index-1; target = target->next, i++);temp = target->next;// 2、target指向temp的后一个节点target->next = temp->next;// 3、释放free(temp);

完整函数片段

/// 删除指定位置的节点/// @param L 链表/// @param index 位置Status ListDelete(LinkList *L, int index){    if (*L == NULL) return ERROR;    // 只剩一个节点    if ((*L)->next == *L) {        free((*L))        (*L) = NULL;        return ERROR;    }    LinkList target , temp;    if (index == 1)    {        // 删除首元节点        // 1、找到尾节点target        for (target = *L; target->next != *L; target = target->next);        temp = *L; // temp要删除的节点        // 2、尾节点指向删除节点后的节点        target->next = (*L)->next;        // 3、首指针指向尾节点后的节点        *L = target->next;        // 4、释放        free(temp);    }    else    {        // 删除其他任意节点        int i;        // 1、找到尾节点target  和 要删除的temp        for (i=1, target = *L; target->next != *L && i < index-1; target = target->next, i++);        temp = target->next;        // 2、target指向temp的后一个节点        target->next = temp->next;        // 3、释放        free(temp);    }    return OK;}

查询

下面的实现代码，本质还是 遍历

根据位置查询值

ElemType FindValue(LinkList L, int index){    int i; // 辅助确定插入位置    LinkList target;    // 1、找到插入位置的前一个节点target    for (i = 1, target = L; target->next != L && i != index-1; i++,target = target->next) ;    return target->next->data;}

根据值查询位置（前提条件：每个节点的存储的值没有重复）

int FindIndex(LinkList L, ElemType v){    int i = 1;    LinkList temp = L;    for (; temp->next!=L && temp->data != v; temp = temp->next,i++) ;    if (temp->next == L && temp->data != v)        return -1;    return i;}

遇到的问题

1、为什么插入、删除都要注意是不是首元节点？

需要变更头指针指向新的首元节点

2、博客外的问题：创建链表时，是不是双指针？具体什么含义？

struct Node *LinkList; // 存储节点实体在内存中的地址，所以指针->实体节点LinkList L;CreateList(&L); // 传指针L的地址 : 指针的指针...Void CreateList(LinkList *pL){    // pL 已经不是上面的L *pL 才是上面的L    // 所以到这里， pL 就是指向L的指针 L指向实体节点    // malloc 函数返回的开辟的内存空间的地址，所以要用指针接收    *pL = (LinkList)malloc(sizeof(Node));    // *pL 里存的就是节点的内存地址    // 所以pL里存的是节点的内存地址的地址}

3、单向链表与单向循环链表的区别

循环链表的尾节点又指向了首元节点，逻辑结构成 环 状