链表（链式存储结构）及创建（C语言详解版）
链表的基本操作（C语言）详解
静态链表及实现（C语言）详解
静态链表基本操作（C语言实现）详解
循环链表(约瑟夫环)的建立及C语言实现
双向链表及其创建（C语言）详解
双向链表基本操作（C语言实现）详解
顺序表和链表的优缺点（区别、特点）详解
存储结构和存取结构，完全不是一码事！
单链表反转（4 种算法实现）
判断两个单链表相交
- 方法1
- 方法2
如何判断链表中有环？
链表应用
- 带头结点的单链表就地逆置
- 两个有序链表序列的合并

链表（链式存储结构）及创建（C语言详解版）

链表是什么

链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的

链表的节点

链表数据储存没有顺序，但也不能让我们无迹可寻吧，所以数据域指我们存入的数据，指针域用来指向下一个数据域，目的是为了有迹可循，说白了就是替代顺序表固有的顺序性质

根据上图容易理解下面的代码，此时但凡被link修饰的皆为节点

typedef struct Link{
     char elem; //代表数据域
     struct Link * next; //代表指针域，指向直接后继元素
  }link; //link为节点名，每个节点都是一个 link 结构体

图片可能会造成误解，其实链表是没有紧密相连的，而是靠着指针域来查找下一个元素

头节点，头指针和首元节点

链表的创建（初始化）

创建一个链表需要做如下工作：

声明一个头指针（如果有必要，可以声明一个头节点）；

创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；

无头节点

link * initLink() {
link * p = NULL;//创建头指针
link * temp = (link*)malloc(sizeof(link));//创建首元节点
//首元节点先初始化
temp->elem = 1;
temp->next = NULL;
p = temp;//头指针指向首元节点
//从第二个节点开始创建
for (int i = 2; i < 5; i++) {
    link *a = (link*)malloc(sizeof(link));//创建一个新节点并初始化
    a->elem = i;
    a->next = NULL;
    temp->next = a; //将temp节点与新建立的a节点建立逻辑关系
    temp = a;//指针temp每次都指向新链表的最后一个节点，其实就是 a节点，这里写temp=a也对(原始代码为temp = temp->next; 我觉得下面这个好理解)
}
//返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表
return p;
}

有头结点

    link * initLink(){
        int i;
        link * p=(link*)malloc(sizeof(link));//创建一个头结点
        link * temp=p;//声明一个指针指向头结点，
        //生成链表
        for (i=1; i<5; i++) {
            link *a=(link*)malloc(sizeof(link));
            a->elem=i;
            a->next=NULL;
            temp->next=a;
            temp=temp->next;
        }
        return p;
    }

无头节点创建、打印链表

    #include <stdio.h>
    #include <stdlib.h>
    //链表中节点的结构
    typedef struct Link {
        int  elem;
        struct Link *next;
    }link;
    //初始化链表的函数
    link * initLink();
    //用于输出链表的函数
    void display(link *p);
    int main() {
        link*p = NULL;
        //初始化链表（1，2，3，4）
        printf("初始化链表为：\n");
        p = initLink();
        display(p);
        return 0;
    }
    link * initLink() {
        int i;
        link * p = NULL;//创建头指针
        link * temp = (link*)malloc(sizeof(link));//创建首元节点
        //首元节点先初始化
        temp->elem = 1;
        temp->next = NULL;
        p = temp;//头指针指向首元节点
        for (i = 2; i < 5; i++) {
            link *a = (link*)malloc(sizeof(link));
            a->elem = i;
            a->next = NULL;
            temp->next = a;
            temp = temp->next;
        }
        return p;
    }
    void display(link *p) {
        link* temp = p;//将temp指针重新指向头结点
        //只要temp指针指向的结点的next不是Null，就执行输出语句。
        while (temp) {
            printf("%d ", temp->elem);
            temp = temp->next;
        }
        printf("\n");
    }

注意，如果使用带有头节点创建链表的方式，则输出链表的 display 函数需要做适当地修改：

    void display(link *p){
        link* temp=p;//将temp指针重新指向头结点
        //只要temp指针指向的结点的next不是Null，就执行输出语句。
        while (temp->next) {
            temp=temp->next;
            printf("%d",temp->elem);
        }
        printf("\n");
    }

链表的基本操作（C语言）详解

注意，以下对链表的操作实现均建立在已创建好链表的基础上，创建链表的代码如下所示：

有头结点

    //声明节点结构
    typedef struct Link {
        int  elem;//存储整形元素
        struct Link *next;//指向直接后继元素的指针
    }link;
    //创建链表的函数
    link * initLink() {
        link * p = (link*)malloc(sizeof(link));//创建一个头结点
        link * temp = p;//声明一个指针指向头结点，用于遍历链表
        int i = 0;
        //生成链表
        for (i = 1; i < 5; i++) {
            //创建节点并初始化
            link *a = (link*)malloc(sizeof(link));
            a->elem = i;
            a->next = NULL;
            //建立新节点与直接前驱节点的逻辑关系
            temp->next = a;
            temp = temp->next;
        }
        return p;
    }


void display(link *p) {
    link* temp = p;//将temp指针重新指向头结点
    //只要temp指针指向的结点的next不是Null，就执行输出语句。
    while (temp) {
        printf("%d ", temp->elem);
        temp = temp->next;
    }
    printf("\n");
}

单链表插入元素

有三种插入元素的可能

  1. 头部插入
  1. 中间插入
  1. 尾部插入

链表插入元素的思想是固定的，只需做以下两步操作，即可将新元素插入到指定的位置：

将新结点的 next 指针指向插入位置后的结点；
将插入位置前结点的 next 指针指向插入结点；

    //p为原链表，elem表示新数据元素，add表示新元素要插入的位置
    link * insertElem(link * p, int elem, int add) {
        link * temp = p;//创建临时结点temp
        link * c = NULL;
        int i = 0;
        //首先找到要插入位置的上一个结点
        for (i = 1; i < add; i++) {
            if (temp == NULL) {
                printf("插入位置无效\n");
                return p;
            }
            temp = temp->next;
        }
        //创建插入结点c
        c = (link*)malloc(sizeof(link));
        c->elem = elem;
        //向链表中插入结点
        c->next = temp->next;
        temp->next = c;
        return  p;
    }

插入元素提出问题

关键的添加代码的理解

c->next = temp->next;    <br />    temp->next = c;

这里我们需要重新拿出那种图片来完全理解

这里拿头结点作为实验，其他地方思路都是一样，代码亦是如此

我们可以看到temp->next本来指向节点1，可节点C要添加进来，就把这份功能赋给了新节点C，所以c->next = temp->next，代表节点C取代temp指向节点1

可这还没完，因为节点temp和节点C要建立逻辑关系，所以temp->next = c就代表节点tem的指针域指向节点C

删除

从链表中删除数据元素需要进行以下 2 步操作：

  1.  将结点从链表中摘下来;
  1. 手动释放掉结点，回收被结点占用的存储空间;

其中，从链表上摘除某节点的实现非常简单，只需找到该节点的直接前驱节点 temp，执行一行程序：

temp->next=temp->next->next;

    //p为原链表，add为要删除元素的值
    link * delElem(link * p, int add) {
        link * temp = p;
        link * del = NULL;
        int i = 0;
        //temp指向被删除结点的上一个结点
        for (i = 1; i < add; i++) {
            temp = temp->next;
        }
        del = temp->next;//单独设置一个指针指向被删除结点，以防丢失
        temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
        free(del);//手动释放该结点，防止内存泄漏
        return p;
    }

删除元素提出问题

核心删除代码的理解

**temp->next=temp->next->next;**

只要看到下面这张图，并且深刻理解temp->next的含义是指向下一个节点，而不是下一个节点的数据域或指针域，你就明白temp->next->next的含义是被删节点的下个节点

比方说temp又名节点2，temp->next代表节点3，temp->next->next代表节点4

为什么需要把要删除的元素单独拿出来释放

大家观察上图，我们的这步操作temp->next=temp->next->next 与其说是删除，不如说是越过被删除的节点，本质上该节点没有被删除，所以我们需要单独把这个地址拿出来，然后用free释放掉

del = temp->next;

free(del);

查找

在链表中查找指定数据元素，最常用的方法是：从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的 NULL（比对失败的标志）

这行代码两点说明：

前面函数都是用 link *修饰这里是int修饰

我的代码和网站代码不同，是因为我这里基于的前提代码没有头结点

    //p为原链表，elem表示被查找元素、
    int selectElem(link * p, int elem) {
        //新建一个指针t，初始化为头指针 p
        link * t = p;
        int i = 1;
        //由于头节点的存在，因此while中的判断为t->next
        while (t->next) {
            t = t->next;
            if (t->elem == elem) {
                return i;
            }
            i++;
        }
        //程序执行至此处，表示查找失败
        return -1;
    }

更改

更新链表中的元素，只需通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可

    //更新函数，其中，add 表示更改结点在链表中的位置，newElem 为新的数据域的值
    link *amendElem(link * p, int add, int newElem) {
        int i = 0;
        link * temp = p;
        temp = temp->next;//在遍历之前，temp指向首元结点
        //遍历到被删除结点
        for (i = 1; i < add; i++) {
            temp = temp->next;
        }
        temp->elem = newElem;
        return p;
    }

总代码

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct Link {
        int  elem;
        struct Link *next;
    }link;
    link * initLink();
    //链表插入的函数，p是链表，elem是插入的结点的数据域，add是插入的位置
    link * insertElem(link * p, int elem, int add);
    //删除结点的函数，p代表操作链表，add代表删除节点的位置
    link * delElem(link * p, int add);
    //查找结点的函数，elem为目标结点的数据域的值
    int selectElem(link * p, int elem);
    //更新结点的函数，newElem为新的数据域的值
    link *amendElem(link * p, int add, int newElem);
    void display(link *p);
    int main() {
        link *p = NULL;
        int address;
        //初始化链表（1，2，3，4）
        printf("初始化链表为：\n");
        p = initLink();
        display(p);
        printf("在第4的位置插入元素5：\n");
        p = insertElem(p, 5, 4);
        display(p);
        printf("删除元素3:\n");
        p = delElem(p, 3);
        display(p);
        printf("查找元素2的位置为：\n");
        address = selectElem(p, 2);
        if (address == -1) {
            printf("没有该元素");
        }
        else {
            printf("元素2的位置为：%d\n", address);
        }
        printf("更改第3的位置上的数据为7:\n");
        p = amendElem(p, 3, 7);
        display(p);
        return 0;
    }
    link * initLink() {
        link * p = (link*)malloc(sizeof(link));//创建一个头结点
        link * temp = p;//声明一个指针指向头结点，用于遍历链表
        int i = 0;
        //生成链表
        for (i = 1; i < 5; i++) {
            link *a = (link*)malloc(sizeof(link));
            a->elem = i;
            a->next = NULL;
            temp->next = a;
            temp = temp->next;
        }
        return p;
    }
    link * insertElem(link * p, int elem, int add) {
        link * temp = p;//创建临时结点temp
        link * c = NULL;
        int i = 0;
        //首先找到要插入位置的上一个结点
        for (i = 1; i < add; i++) {
            if (temp == NULL) {
                printf("插入位置无效\n");
                return p;
            }
            temp = temp->next;
        }
        //创建插入结点c
        c = (link*)malloc(sizeof(link));
        c->elem = elem;
        //向链表中插入结点
        c->next = temp->next;
        temp->next = c;
        return  p;
    }
    link * delElem(link * p, int add) {
        link * temp = p;
        link * del = NULL;
        int i = 0;
        //遍历到被删除结点的上一个结点
        for (i = 1; i < add; i++) {
            temp = temp->next;
        }
        del = temp->next;//单独设置一个指针指向被删除结点，以防丢失
        temp->next = temp->next->next;//删除某个结点的方法就是更改前一个结点的指针域
        free(del);//手动释放该结点，防止内存泄漏
        return p;
    }
    int selectElem(link * p, int elem) {
        link * t = p;
        int i = 1;
        while (t->next) {
            t = t->next;
            if (t->elem == elem) {
                return i;
            }
            i++;
        }
        return -1;
    }
    link *amendElem(link * p, int add, int newElem) {
        int i = 0;
        link * temp = p;
        temp = temp->next;//tamp指向首元结点
        //temp指向被删除结点
        for (i = 1; i < add; i++) {
            temp = temp->next;
        }
        temp->elem = newElem;
        return p;
    }
    void display(link *p) {
        link* temp = p;//将temp指针重新指向头结点
        //只要temp指针指向的结点的next不是Null，就执行输出语句。
        while (temp->next) {
            temp = temp->next;
            printf("%d ", temp->elem);
        }
        printf("\n");
    }

经验教训：我去实验代码的时候，我使用的没有头结点，那是真的麻烦，所以我放弃那种写法，就直接复制了。好在我已经理解了代码的含义

静态链表及实现（C语言）详解

静态链表基本操作（C语言实现）详解

循环链表(约瑟夫环)的建立及C语言实现

循环链表解决了一个问题：从任意一个结点开始，就可以访问所有的结点

初始化一个循环链表

#include <stdio.h>
#include <stdlib.h>
typedef struct node {    //我们这里的循环链表介绍的是单链表组成，所以创建结构体方式和单链表一致
    int number;
    struct node * next;
}person;
person * initLink(int n) {

    person * head = NULL, *cyclic = NULL;
    head = (person*)malloc(sizeof(person));
    head->number = 1;
    head->next = NULL;
    cyclic = head;    
    for (int i = 2; i <= n; i++) {
        person * body = (person*)malloc(sizeof(person));
        body->number = i;
        body->next = NULL;
        cyclic->next = body;
        cyclic = cyclic->next;
    }
    cyclic->next = head;//首尾相连
    return head;
}

循环链表和动态链表唯一不同在于它的首尾连接，这也注定了在使用循环链表时，附带最多的操作就是遍历链表

在遍历的过程中，尤其要注意循环链表虽然首尾相连，但并不表示该链表没有第一个节点和最后一个结点。所以，不要随意改变头指针的指向

接下来对重要代码进行解释

既然理解循环代码的创建，我们来解决一个题目吧

约瑟夫环问题

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct node {
        int number;
        struct node * next;
    }person;
    person * initLink(int n) {
        int i = 0;
        person * head = NULL, *cyclic = NULL;
        head = (person*)malloc(sizeof(person));
        head->number = 1;
        head->next = NULL;
        cyclic = head;
        for (i = 2; i <= n; i++) {
            person * body = (person*)malloc(sizeof(person));
            body->number = i;
            body->next = NULL;
            cyclic->next = body;
            cyclic = cyclic->next;
        }
        cyclic->next = head;//首尾相连
        return head;
    }
    void findAndKillK(person * head, int k, int m) {
        person * p = NULL;
        person * tail = head;
        //找到链表第一个结点的上一个结点，为删除操作做准备
        while (tail->next != head) {
            tail = tail->next;
        }
        p = head;
        //找到编号为k的人
        while (p->number != k) {
            tail = p;
            p = p->next;
        }
        //从编号为k的人开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了，
        while (p->next != p) {
            int i = 0;
            //找到从p报数1开始，报m的人，并且还要知道数m-1的人的位置tail，方便做删除操作。
            for (i = 1; i < m; i++) {
                tail = p;
                p = p->next;
            }
            tail->next = p->next;//从链表上将p结点摘下来
            printf("出列人的编号为:%d\n", p->number);
            free(p);
            p = tail->next;//继续使用p指针指向出列编号的下一个编号，游戏继续
        }
        printf("出列人的编号为:%d\n", p->number);
        free(p);
    }
    int main() {
        int n = 0, k = 0, m = 0;
        person * head = NULL;
        printf("输入圆桌上的人数:");
        scanf("%d", &n);
        head = initLink(n);
        printf("从第几个人开始报数(k>1且k<%d)：", n);
        scanf("%d", &k);
        printf("数到几的人出列：");
        scanf("%d", &m);
        findAndKillK(head, k, m);
        return 0;
    }

接下来对重要代码进行解释

void findAndKillK(person * head,int k,int m){

    person * p = NULL;
    person * tail = head;
    while (tail->next != head){
        tail = tail->next;      /*遍历循环链表，直到最后一个节点，也就是找到链表第一个结点的上一个结点
                                因为是循环链表，所以链表第一个结点的上一个结点就是最后一个节点，也许循环不存在最后一个节点这个说法
                                ，但这样好理解，其操作的意义是为删除操作做准备*/
    }
    p = head;

    //找到编号为K的人
    while (p->number != k ){    //这一步还是好理解的
        tail = p;        //为后面删除做准备
        p = p->next;
    }

    while (p->next != p){   //从编号为k的人开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了

        for (int i = 1; i < m; i++) {   //大家注意读懂题目，喊道2的人退出，因为从本身开始遍历的，所以本身喊1，所以下个节点就喊2，所以这里遍历一次就行

            tail = p;   //为后面删除做准备
            p = p->next;

        }

        tail->next = p->next;   //去除编号节点后，建立处在编号节点前驱和后驱的两个节点
        printf("出列人的编号为:%d\n", p->number);
        free(p);    //释放被删除的编号节点
        p = tail->next; //由题目可知，被删除节点的下个节点就作为开始节点，然后进入下一轮循环

    }

    printf("出列人的编号为:%d\n", p->number);
    free(p);    //释放循环链表，尽管节点就最后一个了


}

双向链表及其创建（C语言）详解

单链表更适合 “从前往后” 找，”从后往前” 找并不是它的强项。

“从后往前”使用双向链表，会更加事半功倍


typedef struct line {

    struct line * prior;    //前指针域
    int data;               //数据
    struct line * next;     //后指针域

}line;

其实学习单链表，创建这个双链表非常简单

同单链表相比，双链表仅是各节点多了一个用于指向直接前驱的指针域。因此，我们可以在单链表的基础轻松实现对双链表的创建。

和创建单链表不同的是，创建双向链表的过程中，每一个新节点都要和前驱节点之间建立两次链接，分别是：

将新节点的 prior 指针指向直接前驱节点；
将直接前驱节点的 next 指针指向新节点；

    line* initLine(line * head) {
        int i = 0;
        line * list = NULL;
        //创建一个首元节点，链表的头指针为head
        head = (line*)malloc(sizeof(line));
        //对节点进行初始化
        head->prior = NULL;
        head->next = NULL;
        head->data = 1;
        //声明一个指向首元节点的指针，方便后期向链表中添加新创建的节点
        list = head;
        for (i = 2; i <= 5; i++) {
            //创建新的节点并初始化
            line * body = (line*)malloc(sizeof(line));

            body->prior = NULL;
            body->next = NULL;
            body->data = i;

            //建立逻辑上的 双向
            list->next = body;
            body->prior = list;

            //list永远指向链表中最后一个节点
            list = list->next;        //list->next等价于body，你可以理解成创建的新节点body覆盖节点list，成功实现新节点的连接
        }
        //返回新创建的链表
        return head;
    }

    #include <stdio.h>
    #include <stdlib.h>
    //节点结构
    typedef struct line {
        struct line * prior;
        int data;
        struct line * next;
    }line;
    //双链表的创建函数
    line* initLine(line * head);
    //输出双链表的函数
    void display(line * head);
    int main() {
        //创建一个头指针
        line * head = NULL;
        //调用链表创建函数
        head = initLine(head);
        //输出创建好的链表
        display(head);
        //显示双链表的优点
        printf("链表中第 4 个节点的直接前驱是：%d", head->next->next->next->prior->data);
        return 0;
    }
    line* initLine(line * head) {
        int i = 0;
        line * list = NULL;
        //创建一个首元节点，链表的头指针为head
        head = (line*)malloc(sizeof(line));
        //对节点进行初始化
        head->prior = NULL;
        head->next = NULL;
        head->data = 1;
        //声明一个指向首元节点的指针，方便后期向链表中添加新创建的节点
        list = head;
        for (i = 2; i <= 5; i++) {
            //创建新的节点并初始化
            line * body = (line*)malloc(sizeof(line));
            body->prior = NULL;
            body->next = NULL;
            body->data = i;
            //新节点与链表最后一个节点建立关系
            list->next = body;
            body->prior = list;
            //list永远指向链表中最后一个节点
            list = list->next;
        }
        //返回新创建的链表
        return head;
    }
    void display(line * head) {
        line * temp = head;
        while (temp) {
            //如果该节点无后继节点，说明此节点是链表的最后一个节点
            if (temp->next == NULL) {
                printf("%d\n", temp->data);
            }
            else {
                printf("%d <-> ", temp->data);
            }
            temp = temp->next;
        }
    }

双向链表基本操作（C语言实现）详解

双向链表添加节点

添加有三种情况

表头
表中
表尾

1) 添加至表头
将新数据元素添加到表头，只需要将该元素与表头元素建立双层逻辑关系即可。

换句话说，假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可：

temp->next=head; head->prior=temp;
将 head 移至 temp，重新指向新的表头；

例如，将新元素 7 添加至双链表的表头，则实现过程如图 2 所示：

图 2 添加元素至双向链表的表头
2) 添加至表的中间位置
同单链表添加数据类似，双向链表中间位置添加数据需要经过以下 2 个步骤，如图 3 所示：
新节点先与其直接后继节点建立双层逻辑关系；
新节点的直接前驱节点与之建立双层逻辑关系；

图 3 双向链表中间位置添加数据元素
3) 添加至表尾
与添加到表头是一个道理，实现过程如下（如图 4 所示）：
找到双链表中最后一个节点；
让新节点与最后一个节点进行双层逻辑关系；

图 4 双向链表尾部添加数据元素

前面讲单链表的时候这三种添加节点情况，我们没有分情况，只是同样的代码就解决了

但是要记住，双链表中，每种都要分情况讨论。书写不同的代码

    //data 为要添加的新数据，add 为添加到链表中的位置
    line * insertLine(line * head, int data, int add) {
        //新建数据域为data的结点
        line * temp = (line*)malloc(sizeof(line));
        temp->data = data;
        temp->prior = NULL;
        temp->next = NULL;
        //插入到链表头，要特殊考虑
        if (add == 1) {
            temp->next = head;
            head->prior = temp;
            head = temp;
        }
        else {
            int i = 0;
            line * body = head;
            //找到要插入位置的前一个结点
            for (i = 1; i < add - 1; i++) {
                body = body->next;
                if (body == NULL) {
                    printf("插入位置有误\n");
                    break;
                }
            }
            if (body) {
                //判断条件为真，说明插入位置为链表尾
                if (body->next == NULL) {
                    body->next = temp;
                    temp->prior = body;
                }
                else {
                    body->next->prior = temp;
                    temp->next = body->next;
                    body->next = temp;
                    temp->prior = body;
                }
            }
        }
        return head;
    }

双向链表删除节点

双链表删除结点时，只需遍历链表找到要删除的结点，然后将该节点从表中摘除即可。

例如，从图 1 基础上删除元素 2 的操作过程如图 5 所示：

图 5 双链表删除元素操作示意图

    //删除结点的函数，data为要删除结点的数据域的值
    line * delLine(line * head, int data) {
        line * temp = head;
        //遍历链表
        while (temp) {
            //判断当前结点中数据域和data是否相等，若相等，摘除该结点
            if (temp->data == data) {
                temp->prior->next = temp->next;
                temp->next->prior = temp->prior;
                free(temp);
                return head;
            }
            temp = temp->next;
        }
        printf("链表中无该数据元素\n");
        return head;
    }

双向链表查找节点

通常，双向链表同单链表一样，都仅有一个头指针。因此，双链表查找指定元素的实现同单链表类似，都是从表头依次遍历表中元素。

    //head为原双链表，elem表示被查找元素
    int selectElem(line * head, int elem) {
        //新建一个指针t，初始化为头指针 head
        line * t = head;
        int i = 1;
        while (t) {
            if (t->data == elem) {
                return i;
            }
            i++;
            t = t->next;
        }
        //程序执行至此处，表示查找失败
        return -1;
    }

双向链表更改节点

更改双链表中指定结点数据域的操作是在查找的基础上完成的。实现过程是：通过遍历找到存储有该数据元素的结点，直接更改其数据域即可

    //更新函数，其中，add 表示更改结点在双链表中的位置，newElem 为新数据的值
    line *amendElem(line * p, int add, int newElem) {
        int i = 0;
        line * temp = p;
        //遍历到被删除结点
        for (i = 1; i < add; i++) {
            temp = temp->next;
            if (temp == NULL) {
                printf("更改位置有误！\n");
                break;
            }
        }
        if (temp) {
            temp->data = newElem;
        }
        return p;
    }

总结

    #include <stdio.h>
    #include <stdlib.h>
    typedef struct line {
        struct line * prior;
        int data;
        struct line * next;
    }line;
    //双链表的创建
    line* initLine(line * head);
    //双链表插入元素，add表示插入位置
    line * insertLine(line * head, int data, int add);
    //双链表删除指定元素
    line * delLine(line * head, int data);
    //双链表中查找指定元素
    int selectElem(line * head, int elem);
    //双链表中更改指定位置节点中存储的数据，add表示更改位置
    line *amendElem(line * p, int add, int newElem);
    //输出双链表的实现函数
    void display(line * head);
    int main() {
        line * head = NULL;
        //创建双链表
        printf("初始链表为：\n");
        head = initLine(head);
        display(head);
        //在表中第 3 的位置插入元素 7
        printf("在表中第 3 的位置插入新元素 7：\n");
        head = insertLine(head, 7, 3);
        display(head);
        //表中删除元素 2
        printf("删除元素 2：\n");
        head = delLine(head, 2);
        display(head);
        printf("元素 3 的位置是：%d\n", selectElem(head, 3));
        //表中第 3 个节点中的数据改为存储 6
        printf("将第 3 个节点存储的数据改为 6：\n");
        head = amendElem(head, 3, 6);
        display(head);
        return 0;
    }
    line* initLine(line * head) {
        int i = 0;
        line * list = NULL;
        head = (line*)malloc(sizeof(line));
        head->prior = NULL;
        head->next = NULL;
        head->data = 1;
        list = head;
        for (i = 2; i <= 3; i++) {
            line * body = (line*)malloc(sizeof(line));
            body->prior = NULL;
            body->next = NULL;
            body->data = i;
            list->next = body;
            body->prior = list;
            list = list->next;
        }
        return head;
    }
    line * insertLine(line * head, int data, int add) {
        //新建数据域为data的结点
        line * temp = (line*)malloc(sizeof(line));
        temp->data = data;
        temp->prior = NULL;
        temp->next = NULL;
        //插入到链表头，要特殊考虑
        if (add == 1) {
            temp->next = head;
            head->prior = temp;
            head = temp;
        }
        else {
            int i = 0;
            line * body = head;
            //找到要插入位置的前一个结点
            for (i = 1; i < add - 1; i++) {
                body = body->next;
                if (body == NULL) {
                    printf("插入位置有误\n");
                    break;
                }
            }
            if (body) {
                //判断条件为真，说明插入位置为链表尾
                if (body->next == NULL) {
                    body->next = temp;
                    temp->prior = body;
                }
                else {
                    body->next->prior = temp;
                    temp->next = body->next;
                    body->next = temp;
                    temp->prior = body;
                }
            }
        }
        return head;
    }
    line * delLine(line * head, int data) {
        line * temp = head;
        //遍历链表
        while (temp) {
            //判断当前结点中数据域和data是否相等，若相等，摘除该结点
            if (temp->data == data) {
                temp->prior->next = temp->next;
                temp->next->prior = temp->prior;
                free(temp);
                return head;
            }
            temp = temp->next;
        }
        printf("链表中无该数据元素\n");
        return head;
    }
    //head为原双链表，elem表示被查找元素
    int selectElem(line * head, int elem) {
        //新建一个指针t，初始化为头指针 head
        line * t = head;
        int i = 1;
        while (t) {
            if (t->data == elem) {
                return i;
            }
            i++;
            t = t->next;
        }
        //程序执行至此处，表示查找失败
        return -1;
    }
    //更新函数，其中，add 表示更改结点在双链表中的位置，newElem 为新数据的值
    line *amendElem(line * p, int add, int newElem) {
        int i = 0;
        line * temp = p;
        //遍历到被删除结点
        for (i = 1; i < add; i++) {
            temp = temp->next;
            if (temp == NULL) {
                printf("更改位置有误！\n");
                break;
            }
        }
        if (temp) {
            temp->data = newElem;
        }
        return p;
    }
    //输出链表的功能函数
    void display(line * head) {
        line * temp = head;
        while (temp) {
            if (temp->next == NULL) {
                printf("%d\n", temp->data);
            }
            else {
                printf("%d->", temp->data);
            }
            temp = temp->next;
        }
    }

顺序表和链表的优缺点（区别、特点）详解

顺序表存储数据，需预先申请一整块足够大的存储空间，然后将数据按照次序逐一存储，数据之间紧密贴合，不留一丝空隙

链表的存储方式与顺序表截然相反，什么时候存储数据，什么时候才申请存储空间，数据之间的逻辑关系依靠每个数据元素携带的指针维持

开辟空间的方式

顺序表——>一次开辟，永久使用（动态数组可以改变存储空间）

链表——->一次开辟存储一个节点的物理空间，需要可以在申请，每次申请一个节点

存储数据个数无法确定或者物理空间紧张以致无法一次性申请到大空间可以使用链表

空间利用率

顺序表利用率显然要高于链表，因为链表空间位置是随机的

时间复杂度

根据顺序表和链表在存储结构上的差异，问题类型主要分为以下 2 类：
1. 问题中主要涉及访问元素的操作，元素的插入、删除和移动操作极少；
2. 问题中主要涉及元素的插入、删除和移动，访问元素的需求很少；

第 1 类问题适合使用顺序表。这是因为，顺序表中存储的元素可以使用数组下标直接访问，无需遍历整个表，因此使用顺序表访问元素的时间复杂度
为 O(1)；而在链表中访问数据元素，需要从表头依次遍历，直到找到指定节点，花费的时间复杂度为 O(n);
链表访问元素时间复杂度—-> O(n)
顺序表访问元素时间复杂度——>O(1)

第 2 类问题则适合使用链表。链表中数据元素之间的逻辑关系靠的是节点之间的指针，当需要在链表中某处插入或删除节点时，只需改变相应节点的
指针指向即可，无需大量移动元素，因此链表中插入、删除或移动数据所耗费的时间复杂度为 O(1)；而顺序表中，插入、删除和移动数据可能会牵涉
到大量元素的整体移动，因此时间复杂度至少为 O(n);

链表中插入、删除或移动数据所耗费的时间复杂度为 ——->O(1)
顺序表中插入、删除和移动数据可能会牵涉到大量元素的整体移动，因此时间复杂度至少为——-> O(n);

综上所述，不同类型的场景，选择合适的存储结构会使解决问题效率成倍数地提高

存储结构和存取结构，完全不是一码事！

存储结构，指的是数据在内存中真实的存储状态

存取结构，指的是存取数据的方式

我们知道线性表本质就是数组

随机存或取数据，举个例子我要把下标2的数据换成4 a[2] = 4 我要取出下标为3的数据 a[3]

显然借助顺序存储结构的特点，我们可以随机存或者取存储的各个元素。这也就解释了“线性表的顺序存储结构，又可以称为随机存取结构”

和随机存取结构相对的，是顺序存取结构。通过前面的学习我们知道，采用链表存储的数据，它们所在的物理空间并不紧挨着，而是分散在内存中的各个位置

如果我们想在链表中存或者取数据，就只能从链表头 H 开始，逐个遍历链表中的每个元素，直至找到目标元素。也就是说，从链表中存和取数据，必须从遵循各个元素在链表中存储的逻辑顺序，无法随机存取

总之，线性表的顺序存储结构，又可以称为随机存取结构；而线性表的链式存储结构（栈和队列），又可以称为顺序存取结构

你只要注意存取二字，再联想顺序表和链表获存取数据的方式一下子就明白

顺序存储结构为随机存取结构

链式存储结构为顺序存取结构

单链表反转（4 种算法实现）

解决不带头节点

递归反转法

解决带头节点和不带头节点皆可

迭代反转法
就地逆置法
头插法

迭代反转链表

递归反转链表

头插法反转链表

就地逆置法反转链表

link * local_reverse(link * head) {
link * beg = NULL;
link * end = NULL;
if (head == NULL || head->next == NULL) {

return head;

} 

beg = head;
end = head->next;
while (end != NULL) {

//将 end 从链表中摘除

beg->next = end->next;

//将 end 移动至链表头

end->next = head;

head = end;

//调整 end 的指向， 另其指向 beg 后的一个节点， 为反转下一个节点做准备

end = beg->next;
} 
return head;
}

判断两个单链表相交

数据域中存储元素值相同，并不是 2 个单链表相交的充分条件，因为 2 个不相交的链表中很可能存有相同的元素

所以我们比较的是链表中的地址

方法1

2 个单链表相交有一个必然结果，即这 2 个链表的最后一个节点必定相同；反之，如果 2 个链表不相交，则这 2 个链表的最后一个节点必定不相同

//L1 和 L2 为 2 个单链表， 函数返回 True 表示链表相交， 返回 False 表示不相交
bool LinkIntersect(link * L1, link * L2) {
link * p1 = L1;
link * p2 = L2;
//找到 L1 链表中的最后一个节点
while (p1->next) {
p1 = p1->next;
} 
//找到 L2 链表中的最后一个节点
while (p2->next)
{
p2 = p2->next;
} 
//判断 L1 和 L2 链表最后一个节点是否相同
if (p1 == p2) {
    return True;
} 
return False;
}

方法2

假设 L1 和 L 2 相交，则两个链表中相交部分节点的数量一定是相等的

可以看到， L1 和 L2 相交，绿色部分节点为 L1 和 L2 链表的相交部分

也就是说，如果 2 个链表相交，那么它们相交部分所包含的节点个数一定相等。

//L1 和 L2 为 2 个单链表， 函数返回 True 表示链表相交， 返回 False 表示不相交
bool LinkIntersect(link * L1, link * L2) {
link * plong = L1;
link * pshort = L2;
link * temp = NULL;
int num1 = 0, num2 = 0, step = 0;
//得到 L1 的长度
while (plong) {
    num1++;
    plong = plong->next;
} 
//得到 L2 的长度
while (pshort)
{
    num2++;
    pshort = pshort->next;
} 
//重置 plong 和 pshort， 使 plong 代表较长的链表， pshort 代表较短的链表
plong = L1;
pshort = L2;
step = num1 - num2;
if (num1 < num2) {
plong = L2;
pshort = L1;
step = num2 - num1;
} 
//在 plong 链表中找到和 pshort 等长度的子链表
temp = plong;
while (step) {
temp = temp->next;
step--;
} 
//逐个比较 temp 和 pshort 链表中的节点是否相同
while (temp && pshort) {
if (temp == pshort) {
return True;
} 
temp = temp->next;
pshort = pshort->next;
} 
return False;
}

如何判断链表中有环？

环链表并不一定就是循环链表。循环链表指的是“首尾相连”的单链表，而有环链表则指的是单链表中存在一个循环子链表

bool HaveRing(link * H) {
link * H1 = H->next;
link * H2 = H;
while (H1)
{
    if (H1 == H2)
{
//链表中有环
    return True;
} 
    else
{
    H1 = H1->next;
    if (!H1)
{
//链表中无环
    return False;
} 
    else
{
    H1 = H1->next;
    H2 = H2->next;
}
}
} 
//链表中无环
return False;
}

链表应用

带头结点的单链表就地逆置

本题要求

本题要求编写函数实现带头结点的单链线性表的就地逆置操作函数。L是一个带头结点的单链表，函数ListReverse_L(LinkList &L)要求在不新开辟节点的前提下将单链表中的元素进行逆置，如原单链表元素依次为1,2,3,4，则逆置后为4,3,2,1。

函数接口定义：

void ListReverse_L(LinkList &L);

裁判测试程序样例

//库函数头文件包含
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int  Status;
typedef int  ElemType; //假设线性表中的元素均为整型

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

Status ListCreate_L(LinkList &L,int n)
{
    LNode *rearPtr,*curPtr;   //一个尾指针，一个指向新节点的指针
    L=(LNode*)malloc(sizeof (LNode));
    if(!L)exit(OVERFLOW);
    L->next=NULL;               //先建立一个带头结点的单链表
    rearPtr=L;  //初始时头结点为尾节点,rearPtr指向尾巴节点
    for (int i=1;i<=n;i++){  //每次循环都开辟一个新节点，并把新节点拼到尾节点后
        curPtr=(LNode*)malloc(sizeof(LNode));//生成新结点
        if(!curPtr)exit(OVERFLOW);
        scanf("%d",&curPtr->data);//输入元素值
        curPtr->next=NULL;  //最后一个节点的next赋空
        rearPtr->next=curPtr;
        rearPtr=curPtr;
    }
    return OK;
}
void ListReverse_L(LinkList &L);
void ListPrint_L(LinkList &L){
//输出单链表
    LNode *p=L->next;  //p指向第一个元素结点
    while(p!=NULL)
    {
          if(p->next!=NULL)
               printf("%d ",p->data);
          else
               printf("%d",p->data);
          p=p->next;
    }
}
int main()
{
    LinkList L;
    int n;
    scanf("%d",&n);
    if(ListCreate_L(L,n)!= OK) {
          printf("表创建失败！！！\n");
          return -1;
    }
    ListReverse_L(L);
    ListPrint_L(L);
    return 0;
}
/* 请在这里填写答案 */

[

](https://blog.csdn.net/m0_38015368/article/details/78058397)

void ListReverse_L(LinkList &L){

    LNode * begin = NULL ;
    LNode * end   = NULL;
    begin = L->next;    
    end   = begin->next;
    if(begin != NULL && end != NULL){

        while (end != NULL ){
            begin->next = end->next;    
            end->next = L->next;        
            L->next = end;            
            end = begin->next;
        }
    }
}

前面我们学习过就地逆置法，但这里的代码有所不同，因为这里有头节点，这是你要注意的

03--链表