0
0

单链表详解（两万字细节讲解，头插法尾插法，删除交换，翻转）

    最近有很多同学在学习链表，因此特地出一期详细的链表教学，当然最重要的还是自己**亲手敲一遍**才能深刻理解。最好还能跟**上手画草图**，可以更好的理解链表的实现过程。
     相信既然学到链表应该都对函数有所了解，因此今天以函数的形式来进行操作，同时**大部分解释以注释的形式与代码在一起**。
     那么话不多说，直接进入今天的主题——单链表。

主要函数malloc、free

    malloc函数是包含于stdlib.h头文件下的一个库函数，其作用是在堆区申请开辟一块空间，如果不理解的话，可以简单理解为malloc创建出来之后在程序结束之前就不会消失，相当于全局变量。其用法如下：


void* malloc (size_t size);

分配内存块

分配一个字节内存块，返回指向该块开头的指针。

新分配的内存块的内容未初始化，剩余为不确定值。

如果为零，则返回值取决于特定的库实现（它可能是空指针，也可能不是空指针），但不应取消引用返回的指针。

括号内的即为开辟空间的大小，以字节为单位，如int类型为4.

    free同样包含于stdlib.h头文件下，其作用是释放malloc开辟的空间。很多同学并不理解，认为实际上很多时候忘记加free也没有出现bug，但是建议养成一个良好的习惯。假设有一台服务器，需要存放玩家数据，每次都是用malloc分配，如果数据不用之后不对其空间进行free，那么长久下来，系统的堆区就变得很小，导致了卡顿，雀氏重启可以自动释放，但是对于一个需要持续运行的服务器，每隔几天重启一次，那么已经存放的玩家数据怎么办？所以希望同学们能重视这一个细节

void free (void* ptr);

解除分配内存块

释放先前由malloc等调用分配的内存块，使其再次可用于进一步分配。

如果不指向为上述函数分配的内存块，则会导致未定义的行为。

if 是空指针，则该函数不执行任何操作。

尾插法

头插法

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明

int main()
{
    int length = 0; //用于输入链表期望的长度
    list* head = (list*)malloc(sizeof(list)); //开辟空间时，将malloc返回的指针强制转换为结构体的指针
    scanf("%d", &length); 
    head = list_make(head, length);
    list* head0 = NULL; //用于代替头节点的移动
    head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
    while (head0 != NULL)
    {
        printf("%d", head0->num);
        head0 = head0->next;
    }
    return 0;
}

list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
    int i = 0; //相比于尾插法，头插法不需要记录头指针的位置，因为头指针的不断更新的
    head->next = NULL; //循环开始之前head就是链表的末尾，此操作为将链表末尾设置为NULL，标志链表的结束
    for (i = 0; i < length; i++)
    {
        scanf("%d", &head->num); //输入数据,将输入放在这里是为了更好的体现头插法的特点-》不断向前申请结点
        list* node = (list*)malloc(sizeof(list)); //创建一个结点
        node->next = head; //该结点在head的后面，也就是head->next
        head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
    }
    return head; //返回头节点
}

增加结点

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_add(list* head, int n);

int main()
{
    int n; //用于输入想增加的结点的位置
    scanf("%d", &n); //注意范围为 0 <= n <= length
    list* head = (list*)malloc(sizeof(list));
    head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
    head = list_add(head, n);
    list* head0 = NULL; //用于代替头节点的移动
    head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
    while (head0 != NULL)
    {
        printf("%d ", head0->num);
        head0 = head0->next;
    }
    return 0;
}

list* list_make(list* head, int length)
{
    int i = 0;
    head->next = NULL;
    for (i = 0; i < length; i++)
    {
        head->num = i;
        list* node = (list*)malloc(sizeof(list));
        node->next = head;
        head = node;
    }
    return head;
}

list* list_add(list* head, int n)
{
    list* head0 = head; //代替头指针的移动
    for (; n; n--) //移动到需要增加的结点处
    {
        //例如要在第 n 个结点出增加结点，由于头结点不含数据，因此移动n次即第n个结点
        head0 = head0->next;
    }
    list* node = (list*)malloc(sizeof(list)); //申请开辟空间
    scanf("%d", &node->num);
    node->next = head0->next;
    head0->next = node; //顺序不要错了，不然会丢失掉第n + 1个结点的位置哦
    return head;
}

** 总结起来，头插法存放数据是逆序，尾插法则是正序**

删除结点

正序删除第n个结点

  1. 移除链表元素 - 力扣（LeetCode） (leetcode-cn.com)

  2. 删除链表中的节点 - 力扣（LeetCode） (leetcode-cn.com)

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_delete(list* head, int n);

int main()
{
    int n; //用于输入想删除的结点的位置
    scanf("%d", &n);
    list* head = (list*)malloc(sizeof(list)); 
    head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
    head = list_delete(head, n);
    list* head0 = NULL; //用于代替头节点的移动
    head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
    while (head0 != NULL)
    {
        printf("%d", head0->num);
        head0 = head0->next;
    }
    return 0;
}

list* list_make(list* head, int length) 
{
    int i = 0; 
    head->next = NULL; 
    for (i = 0; i < length; i++)
    {
        head->num = i; 
        list* node = (list*)malloc(sizeof(list)); 
        node->next = head; 
        head = node; 
    }
    return head; 
}

list* list_delete(list* head, int n)
{
    list* head0 = head; //代替头指针的移动
    for (--n; n; n--) //删除结点的时候需要移动到该结点前一个结点
    {
        //例如要删除第 n 个结点,则在第n - 1个结点处停下，到这里或许你能理解为什么说头节点通常不存放数据了
        //该循环的意思是先将n-1，表示整个过程需要移动n-1下，判断条件n是n不为0,就是说n不断-1,直到为0就移动到第n-1个结点了
        head0 = head0->next;
    }
    list* node = head0->next; //记录下需要删除的结点的位置
    head0->next = node->next; 
    //此处是最容易发生错误的，很多初学者会将指针移动到正好第n个结点，然后head = head->next
    //乍一看两者一样，但是head = head->next是head这一个指针的移动，而实际上各个指针域并没有发生改变
    //但是head0->next = node->next 是一个对head0->next的赋值操作，也就是改变了head0的指针域
    free(node); //释放掉之前该结点malloc申请的空间
    return head;
}

** 关键：移动到第n - 1个结点**

逆序删除第n个结点

  1. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)

常规删除（遍历链表两遍）

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_delete(list* head, int n);

int main()
{
    int n; //用于输入想逆序删除的结点的位置
    scanf("%d", &n);
    list* head = (list*)malloc(sizeof(list)); 
    head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
    head = list_delete(head, n);
    list* head0 = NULL; //用于代替头节点的移动
    head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
    while (head0 != NULL)
    {
        printf("%d", head0->num);
        head0 = head0->next;
    }
    return 0;
}

list* list_make(list* head, int length) 
{
    int i = 0; 
    head->next = NULL; 
    for (i = 0; i < length; i++)
    {
        head->num = i; 
        list* node = (list*)malloc(sizeof(list)); 
        node->next = head; 
        head = node; 
    }
    return head; 
}

list* list_delete(list* head, int n)
{
    int length = 0; //用于记录链表的长度
    list* head0 = head->next; //代替头指针的移动
    while (head0 != NULL)
    {
        ++length; //head0每移动一次length就+1,最后可以得出链表的长度
        head0 = head0->next;
    }
    for (head0 = head, length -= n; length; length--) //将head0指向head, 循环其余设可以参考正序删除第n个结点的设置
    {
        //倒数第n个就是正数第length-n+1个结点，举例：length = 10, n = 2, 那么就是第 10-2+1=9第9个结点
        head0 = head0->next;
    }
    list* node = head0->next;
    head0->next = node->next;
    free(node); 
    return head;
}

存入结构体指针数组（遍历链表一遍）

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_delete(list* head, int n);

int main()
{
    int n; //用于输入想逆序删除的结点的位置
    scanf("%d", &n);
    list* head = (list*)malloc(sizeof(list)); 
    head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
    head = list_delete(head, n);
    list* head0 = NULL; //用于代替头节点的移动
    head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
    while (head0 != NULL)
    {
        printf("%d", head0->num);
        head0 = head0->next;
    }
    return 0;
}

list* list_make(list* head, int length) 
{
    int i = 0; 
    head->next = NULL; 
    for (i = 0; i < length; i++)
    {
        head->num = i; 
        list* node = (list*)malloc(sizeof(list)); 
        node->next = head; 
        head = node; 
    }
    return head; 
}

#define my_max 100

list* list_delete(list* head, int n)
{
    list* arr[my_max], * head0 = head;
    //建立一个结构体指针数组保存各个结点的位置，head0来遍历链表
    int i = 0;
    while (head0 != NULL)
    {
        arr[i] = head0;
        i++;// i用于记录结点个数，但要注意会把头结点记录进去（我的头结点未存放数据）
        head0 = head0->next;//head0向后移动
    }
    arr[i] = head0; //最后将NULL记录入数组
    arr[i - n - 1]->next = arr[i - n + 1]; //直接利用数组记录结点进行操作，不用再次遍历
    free(arr[i - n]); // 记得释放空间
    return head;
}

动态规划滑动窗口双指针（遍历链表一遍）

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_delete(list* head, int n);

int main()
{
    int n; //用于输入想逆序删除的结点的位置
    scanf("%d", &n);
    list* head = (list*)malloc(sizeof(list)); 
    head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
    head = list_delete(head, n);
    list* head0 = NULL; //用于代替头节点的移动
    head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
    while (head0 != NULL)
    {
        printf("%d", head0->num);
        head0 = head0->next;
    }
    return 0;
}

list* list_make(list* head, int length) 
{
    int i = 0; 
    head->next = NULL; 
    for (i = 0; i < length; i++)
    {
        head->num = i; 
        list* node = (list*)malloc(sizeof(list)); 
        node->next = head; 
        head = node; 
    }
    return head; 
}

#define my_max 100

list* list_delete(list* head, int n)
{
    list* r = NULL, * l = NULL; //设置两个左右指针
    r = head, l = head; //先置于头结点
    while (n--)
        r = r->next; //r移动n个结点，此时l - r之间存在n个结点
    while (r->next)
    {
        r = r->next;
        l = l->next;
        // r, l均向后移，直到r的下一个结点是链表末尾，此时由于l - r之间存在n个结点
        //因此r恰好指向到数第n + 1个结点
    }
    r = l->next;//r此时记录下需要释放内存的地点
    l->next = l->next->next; //删除节点
    free(r); //释放内存
    return head;
}

交换结点

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_exchange(list* head, int a, int b);

int main()
{
    int a, b; //用于输入想增加的结点的位置
    scanf("%d%d", &a, &b);
    list* head = (list*)malloc(sizeof(list));
    head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
    head = list_exchange(head, a, b);
    list* head0 = NULL; //用于代替头节点的移动
    head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
    while (head0 != NULL)
    {
        printf("%d ", head0->num);
        head0 = head0->next;
    }
    return 0;
}

list* list_make(list* head, int length)
{
    int i = 0;
    head->next = NULL;
    for (i = 0; i < length; i++)
    {
        head->num = i;
        list* node = (list*)malloc(sizeof(list));
        node->next = head;
        head = node;
    }
    return head;
}

list* list_exchange(list* head, int a, int b)
{
    if (a > b) //统一大小顺序，方便交换
    {
        int t = a;
        a = b;
        b = t;
    }
    int i = 0;
    list* head0 = head, * exc1 = NULL, * exc2 = NULL; //代替头指针的移动
    while (head0) //移动到需要增加的结点处
    {
        if (i + 1 == a)
            exc1 = head0;
        if (i + 1 == b)
            exc2 = head0; //分别找到需要交换的两个结点的前一个结点
        i++;
        head0 = head0->next;
    }
    list* a1 = exc1, * a2 = exc1->next->next, * b1 = exc2, * b2 = exc2->next->next; //几下两个结点左右的结点
    exc1 = exc1->next, exc2 = exc2->next;//将exc1,exc2变为被交换的结点，此方法最笨，但是最容易理解掌握
    if (abs(a - b) != 1)//相邻结点的交换与不相邻的结点交换不同
    {
        a1->next = exc2, exc2->next = a2, b1->next = exc1, exc1->next = b2;
    }
    else
    {
        a1->next = exc2, exc2->next = exc1, exc1->next = b2;
    }
    return head;
}

倒序输出数据域（采用存入一个大数组中）

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
void list_reprintf(list* head);

int main()
{
    list* head = (list*)malloc(sizeof(list)); 
    head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
    list* head0 = NULL; //用于代替头节点的移动
    head0 = head->next; //通常头结点不用于存放数据，当然也可以存放，看个人习惯
    printf("链表原本为："); //打印原链表顺序，方便对比
    while (head0 != NULL)
    {
        printf("%d", head0->num);
        head0 = head0->next;
    }
    printf("\n");
    list_reprintf(head);
    return 0;
}

list* list_make(list* head, int length) 
{
    int i = 0; 
    head->next = NULL; 
    for (i = 0; i < length; i++)
    {
        head->num = i; 
        list* node = (list*)malloc(sizeof(list)); 
        node->next = head; 
        head = node; 
    }
    return head; 
}

#define my_max 100

void list_reprintf(list* head)
{
    printf("逆序输出为：");
    int arr[my_max] = { 0 }, i = 0; //定义一个大数组（元素大于给出链表的结点上限）
    list* head0 = head->next; // 用head0来代替头指针移动，防止head指向位置发生改变而找不到头结点
    while (head0)
    {
        arr[i++] = head0->num; //顺序存入数组
        head0 = head0->next;
    }
    while (i)
        printf("%d", arr[--i]); //i此时为元素上限，逆序输出数组即可
}

升序链表合并

两个升序链表合并

  1. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)

正常逐个判断

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_merge(list* head1, list* head2);

int main()
{
    int length = 0; //用于输入链表期望的长度
    list* head1 = (list*)malloc(sizeof(list));
    scanf("%d", &length);
    head1 = list_make(head1, length);//创建链表1
    list* head2 = (list*)malloc(sizeof(list));
    scanf("%d", &length);
    head2 = list_make(head2, length);//创建链表2
    list* head = list_merge(head1->next, head2->next); //合并的时候从有数据的开始，因此传入头结点之后的一个结点
    while (head->next)
    {
        head = head->next;
        printf("%d\n", head->num);
    }
    return 0;
}

list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
    int i = 0;
    list* head0 = head;    //创建一个head0来记录head头节点的位置，便于返回
    for (i = 0; i < length; i++)
    {
        list* node = (list*)malloc(sizeof(list)); //创建一个结点
        head->next = node; //该结点在head的后面，也就是head->next
        head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
        scanf("%d", &head->num);
    }
    head->next = NULL; //循环结束后head应该在链表的末尾，此操作为将链表末尾设置为NULL，标志链表的结束
    return head0; //返回头节点
}

list* list_merge(list* head1, list*head2)
{
    list* head  = (list*)malloc(sizeof(list)); //创建一个新的头结点作为合并后的新头结点
    list* head0 = head; //记录下头结点的位置
    while (head1 && head2) //只要一个链表到达尾部，即停止
    {
        if (head1->num >= head2->num) //比较并衔接
        {
            head->next = head2;
            head2 = head2->next;
        }
        else if (head1->num < head2->num)
        {
            head->next = head1;
            head1 = head1->next;
        }
        head = head->next;
    }
    if (head1 == NULL) //到达尾部之后只需把另一个链表衔接到尾部即可
        head->next = head2;
    else if (head2 == NULL)
        head->next = head1;
    return head0;
}

递归

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_merge(list* head1, list* head2);

int main()
{
    int length = 0; //用于输入链表期望的长度
    list* head1 = (list*)malloc(sizeof(list));
    scanf("%d", &length);
    head1 = list_make(head1, length);//创建链表1
    list* head2 = (list*)malloc(sizeof(list));
    scanf("%d", &length);
    head2 = list_make(head2, length);//创建链表2

    return 0;
}

list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
    int i = 0;
    list* head0 = head;    //创建一个head0来记录head头节点的位置，便于返回
    for (i = 0; i < length; i++)
    {
        list* node = (list*)malloc(sizeof(list)); //创建一个结点
        head->next = node; //该结点在head的后面，也就是head->next
        head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
        scanf("%d", &head->num);
    }
    head->next = NULL; //循环结束后head应该在链表的末尾，此操作为将链表末尾设置为NULL，标志链表的结束
    return head0; //返回头节点
}

list* list_merge(list* head1, list*head2)
{
    if (head1 == NULL) //遇到NULL则直接返回另一个链表剩下的即可
        return head2;
    if (head2 == NULL)
        return head1;
    if (head1->num < head2->num) //head1 < head2注定返回head1
    {
        head1->next = list_merge(head1->next, head2); //递归判断下一个结点
        return head1;
    }
    else 
    {
        head2->next = list_merge(head1, head2->next);
        return head2;
    }
}

K个正序链表合并

  1. 合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com)

同时判断k个数字（时间最长）

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_merge(list** lists, int size);

int main()
{
    list* node[10];
    int x = 0, y = 0, i = 0; //用于输入链表期望的长度
    scanf("%d", &x);
    for (i = 0; i < x; i++)
    {
        scanf("%d", &y);
        node[i] = (list*)malloc(sizeof(list));
        node[i] = list_make(node[i], y); //创建链表
    }
    list* head = list_merge(node, x);
    while (head && head->next)
    {
        head = head->next;
        printf("%d\n", head->num);
    }
    printf("NULL");
    return 0;
}

list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
    if (length == 0)
        return NULL;
    int i = 0;
    list* head0 = head;    //创建一个head0来记录head头节点的位置，便于返回
    for (i = 0; i < length - 1; i++) //由于要从头结点开始记录数据，故循环次数-1
    {
        scanf("%d", &head->num);
        list* node = (list*)malloc(sizeof(list)); //创建一个结点
        head->next = node; //该结点在head的后面，也就是head->next
        head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
    }
    scanf("%d", &head->num); // 输入最后一个结点的数据
    head->next = NULL;
    return head0; //返回头节点
}

list* list_merge(list** lists, int size)
{
    list* head = (list*)malloc(sizeof(list)); //首先创建一个头结点
    if (size == 0) //如果size为0，返回NULL
        return NULL;
    else if (size == 1) //如果只有一个链表，直接返回该链表
    {
        head->next = lists[0];
        return head;
    }
    int i = 0, k = 0; //i用于遍历每一个链表的第一个值，k用于保存是哪一条链表
    list* head0 = head, * p = NULL;
    while (1) //死循环的意思
    {
        for (p = NULL, i = 0; i < size; i++) //每次先将p赋值为lists中第一个有效的值
            if (lists[i])
                p = lists[i];
        if (!p) //如果没有找到有效的值，说明所有链表以及遍历完成，返回head0
        {
            head->next = NULL;
            return head0;
        }
        for (i = 0; i < size; i++)
        {
            if (lists[i])
                p = p->num < lists[i]->num ? p :(k = i, lists[i]); //三目运算符与逗号表达式
        }
        if (lists[i] != NULL)
        {
            list* node = (list*)malloc(sizeof(list)); //创建一个结点来保存新的数据
            head->next = node;
            head = head->next;
            head->num = p->num; //将p记录的结点的数据赋值给到新链表
            lists[k] = lists[k]->next; //数据被使用的链表向后移动一个结点
        }
    }
}

先合并两个链表，再不断将得到的新链表与其他链表合并（时间较长，优化较小）

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_merge_of_two(list* head1, list* head2);
list* list_merge_of_k(list** lists, int size);

int main()
{
    list* node[10];
    int x = 0, y = 0, i = 0; //用于输入链表期望的长度
    scanf("%d", &x);
    for (i = 0; i < x; i++)
    {
        scanf("%d", &y);
        node[i] = (list*)malloc(sizeof(list));
        node[i] = list_make(node[i], y); //创建链表
    }
    list* head = list_merge_of_k(node, x);
    while (head && head->next)
    {
        head = head->next;
        printf("%d ", head->num);
    }
    printf("NULL");
    return 0;
}

list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
    if (length == 0)
        return NULL;
    int i = 0;
    list* head0 = head;    //创建一个head0来记录head头节点的位置，便于返回
    for (i = 0; i < length - 1; i++) //由于要从头结点开始记录数据，故循环次数-1
    {
        scanf("%d", &head->num);
        list* node = (list*)malloc(sizeof(list)); //创建一个结点
        head->next = node; //该结点在head的后面，也就是head->next
        head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
    }
    scanf("%d", &head->num); // 输入最后一个结点的数据
    head->next = NULL;
    return head0; //返回头节点
}

list* list_merge_of_two(list* head1, list* head2)
{
    list* head = (list*)malloc(sizeof(list));
    list* head0 = head;
    while (head1 || head2)
    {
        list* head = (list*)malloc(sizeof(list)); //创建一个新的头结点作为合并后的新头结点
        list* head0 = head; //记录下头结点的位置
        while (head1 && head2) //只要一个链表到达尾部，即停止
        {
            if (head1->num >= head2->num) //比较并衔接
            {
                head->next = head2;
                head2 = head2->next;
            }
            else if (head1->num < head2->num)
            {
                head->next = head1;
                head1 = head1->next;
            }
            head = head->next;
        }
        if (head1 == NULL) //到达尾部之后只需把另一个链表衔接到尾部即可
            head->next = head2;
        else if (head2 == NULL)
            head->next = head1;
        return head0;
    }
}

list* list_merge_of_k(list** lists, int size)
{
    list* fin = (list*)malloc(sizeof(list)); //创建新链表的头结点
    if (size == 0)
        return NULL;
    else if (size == 1)
    {
        fin->next = lists[0];
        return fin;
    }
    int i = 2;
    fin = list_merge_of_two(lists[0], lists[1]); //先将两条链表合并
    //在此调用之前写的合并两个链表的函数
    while (i < size)
    {
        fin = list_merge_of_two(fin->next, lists[i]); 
        //逐一将剩下的链表合并进来，注意两个链表合并是从有数据的头结点开始的
        i++;
    }
    return fin;
}

每两个链表为一组，不断向下合成新链表（时间最短，优化巨大）

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_merge_of_two(list* head1, list* head2);
list* list_merge_of_k(list** lists, int size);

int main()
{
    list* node[10];
    int x = 0, y = 0, i = 0; //用于输入链表期望的长度
    scanf("%d", &x);
    for (i = 0; i < x; i++)
    {
        scanf("%d", &y);
        node[i] = (list*)malloc(sizeof(list));
        node[i] = list_make(node[i], y); //创建链表
    }
    list* head = list_merge_of_k(node, x);
    while (head && head->next)
    {
        head = head->next;
        printf("%d ", head->num);
    }
    printf("NULL");
    return 0;
}

list* list_make(list* head, int length) //list*类型的函数，返回一个结构体指针
{
    if (length == 0)
        return NULL;
    int i = 0;
    list* head0 = head;    //创建一个head0来记录head头节点的位置，便于返回
    for (i = 0; i < length - 1; i++) //由于要从头结点开始记录数据，故循环次数-1
    {
        scanf("%d", &head->num);
        list* node = (list*)malloc(sizeof(list)); //创建一个结点
        head->next = node; //该结点在head的后面，也就是head->next
        head = node; //将head向后移动到新的结点的位置，然后重复上述步骤
    }
    scanf("%d", &head->num); // 输入最后一个结点的数据
    head->next = NULL;
    return head0; //返回头节点
}

list* list_merge_of_two(list* head1, list* head2)
{
    list* head = (list*)malloc(sizeof(list));
    list* head0 = head;
    while (head1 || head2)
    {
        list* head = (list*)malloc(sizeof(list)); //创建一个新的头结点作为合并后的新头结点
        list* head0 = head; //记录下头结点的位置
        while (head1 && head2) //只要一个链表到达尾部，即停止
        {
            if (head1->num >= head2->num) //比较并衔接
            {
                head->next = head2;
                head2 = head2->next;
            }
            else if (head1->num < head2->num)
            {
                head->next = head1;
                head1 = head1->next;
            }
            head = head->next;
        }
        if (head1 == NULL) //到达尾部之后只需把另一个链表衔接到尾部即可
            head->next = head2;
        else if (head2 == NULL)
            head->next = head1;
        return head0;
    }
}

list* list_merge_of_k(list** lists, int size)
{
    list* fin[10000];//创建一个数组存放合并之后的各个新链表头结点
    if (size == 0)
        return NULL;
    else if (size == 1)
    { 
        fin[0] = (list*)malloc(sizeof(list));
        fin[0]->next = lists[0];
        return lists[0];
    int i = 0, all = size;
    while (i < all)
        fin[i++] = lists[i];//先将链表均存放入数组
    while (all != 1)
    {
        i = 0;
        while (i < all / 2)
        {
            fin[i] = list_merge_of_two(fin[2 * i], fin[2 * i + 1]);
            //继续调用合并两个链表的函数
            //每次相邻的两个合并到i中,由于两个一合并，所以存入i不会引发冲突
            i++;
        }
        if (all % 2)//判断当前余下的新链表（奇数时最后一个链表会多出来）
        {
            fin[i] = fin[all - 1];//存入最后一个数组
            all = (all + 1) / 2;
        }
        else
            all /= 2;
    }
    return fin[0];//最后所有数组合并到fin[0]
}

翻转链表

整个链表反转，如123变为321

  1. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)
#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_reverse_by_total(list* head, list* tail);

int main()
{
    list* head = (list*)malloc(sizeof(list));
    head = list_make(head, 10); //先用头插法创建一个长度为10的链表，其中降序存放0-9
    list* head0 = NULL; //用于寻找尾结点
    while (head0 != NULL)
        head0 = head0->next; //找到该链表的尾节点
    head0 = list_reverse_by_total(head->next, head0);
    while (head0 != NULL)
    {
        printf("%d ", head0->num);
        head0 = head0->next;
    }
    return 0;
}

list* list_make(list* head, int length)
{
    int i = 0;
    head->next = NULL;
    for (i = 0; i < length; i++)
    {
        head->num = i;
        list* node = (list*)malloc(sizeof(list));
        node->next = head;
        head = node;
    }
    return head;
}

list* list_reverse_by_total(list* a, list* b) //给定头指针和尾指针，将整个链表翻转
{
    list* tail = NULL; //默认将翻转后链表的尾指针指向NULL
    list* mid = a;
    list* head = a;
    while (mid != b)
    {
        head = mid->next;
        //整个过程就是head先根据mid找到下一个结点，然后mid不断指向head，最后tail,mid依次后移，重复过程
        mid->next = tail;
        tail = mid;
        mid = head;
    }
    return tail; //mid和head最后都指向下一组的头结点，而mid则是实际上这一组的头结点
}

k个为一组，翻转链表

  1. 两两交换链表中的节点 - 力扣（LeetCode） (leetcode-cn.com)

  2. 合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com)

较复杂但相对比较容易理解想到

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_reverse_k(list* head, int k);
list* list_reverse_two(list* head);

int main()
{
    int length = 0, n = 0; //链表的长度与多少个为一组翻转
    scanf("%d%d", &length, &n);
    list* head = (list*)malloc(sizeof(list));
    head = list_make(head, length);
    head = list_reverse_k(head->next, n);//传入有数据的头结点
    while (head)
    {
        printf("%d ", head->num);
        head = head->next;
    }
    printf("NULL");
    return 0;
}

list* list_make(list* head, int length) 
{
    int i = 0;
    list* head0 = head;
    for (i = 0; i < length; i++)
    {
        list* node = (list*)malloc(sizeof(list)); 
        head->next = node;
        head = node; 
        head->num = i;
    }
    head->next = NULL;
    return head0; 
}

list* list_reverse_k(list* head, int k)
{
    if (k == 1 || head == NULL)
        return head;
    if (k == 2)
        return list_reverse_two(head); //本代码无法单独解决两个一组反转，因此另写一组函数
    int i = 0;
    list* new_head = head, * last_tail = head, * l = head, * m = head->next, * r = head->next->next, * head0 = NULL;
    for (i = 0; i < k && new_head; i++)
        new_head = new_head->next;//确保剩下的可以翻转，并找到下一组的起点
    if (i != k)
        return head;//总结点的不满足k的情况
    for (i = 3; i < k; i++)
    {
        m->next = l; //m不断向后指向l,r不断顺链表移动
        l = m;
        m = r;
        r = r->next;
    }
    r->next = m;
    m->next = l;//最后再将r，m,l连接，这也就是为什么本代码无法单独解决两个一组的翻转
    head0 = r; //单独将第一组翻转拿出来找到返回值的头结点
    list* tail = NULL;//用于记录下一组翻转的链表的起点（翻转后变为终点）
    while (1)
    {
        tail = r = m = l = new_head; //指向新的起点
        for (i = 0; i < k && new_head; i++)
            new_head = new_head->next;//检验剩余结点数量是否满足k
        if (i != k )
            break;
        m = m->next, r = r->next->next;//l,m,r继续呈连续三个结点
        for (i = 3; i < k; i++)//l,m,r三个结点最后相连，因此i从3开始计数
        {
            m->next = l;//重复上述步骤
            l = m;
            m = r;
            r = r->next;
        }
        r->next = m;
        m->next = l;
        last_tail->next = r; //将上一组的结尾连接到这一组翻转后的起点
        last_tail = tail;//同时上一组的尾指针移动到这一组翻转后的尾部，充当下一次的“上一组的尾指针”
    }
    last_tail->next = tail;  //若不满足k或刚好满足k，都可以是看作新的一组未翻转前的起点与上一组的尾结点相连
    return head0;
}

list* list_reverse_two(list* head)
{
    if (head == NULL || head->next == NULL)
        return head; //无法翻转的情况直接返回链表起点
    list* a = head, * b = head->next, * c = head->next->next; 
    head = head->next; //一旦没有直接推出就可以翻转，设置head为翻转后的头结点位置
    while (c != NULL && c->next != NULL)  //满足此情况时，表示至少还存在两个非NULL结点，因此可以翻转
    {
        c = b->next;
        b->next = a;
        if (c != NULL && c->next != NULL) //如果c改变位置后，链表之后还存在两个非NULL结点，则继续移动a,b,否则退出
        {
            b = c->next;
            a->next = b;
            a = c;
        }
    }
    a->next = c;  //将不可翻转的剩余的部分衔接到翻转之后的链表上
    return head;
}

较简单（递归）

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist //结构体的定义
{
    int num; //数据域
    struct linklist* next; //指针域
}list;

list* list_make(list* head, int length); //函数的声明
list* list_reverse_by_total(list* a, list* b);
list* list_reverse_by_k(list* head, int k);

int main()
{
    int length = 0, n = 0; //链表的长度与多少个为一组翻转
    scanf("%d%d", &length, &n);
    list* head = (list*)malloc(sizeof(list));
    head = list_make(head, length);
    head = reverseKGroup(head->next, n);//传入有数据的头结点
    while (head)
    {
        printf("%d ", head->num);
        head = head->next;
    }
    printf("NULL");
    return 0;
}

list* list_make(list* head, int length) 
{
    int i = 0;
    list* head0 = head;
    for (i = 0; i < length; i++)
    {
        list* node = (list*)malloc(sizeof(list)); 
        head->next = node;
        head = node; 
        head->num = i;
    }
    head->next = NULL;
    return head0; 
}

list* list_reverse_by_total(list* a, list* b) //给定头指针和尾指针，将整个链表翻转（在此为一组）
{
    list* tail = NULL; //默认将翻转后链表的尾指针指向NULL
    list* mid = a;
    list* head = a;
    while (mid != b) 
    {
        head = mid->next;
        //整个过程就是head先根据mid找到下一个结点，然后mid不断指向head，最后tail,mid依次后移，重复过程
        mid->next = tail;
        tail = mid;
        mid = head; 
    }
    return tail; //mid和head最后都指向下一组的头结点，而mid则是实际上这一组的头结点
}

list* list_reverse_by_k(list* head, int k) 
{
    if (!head) //如果是空链表就直接return
        return head;
    list* next_head = head; //记录下一组的头结点
    for (int i = 0; i < k; i++) 
    {
        if (!next_head)
            return head; //若未循环完说明就到NULL，说明不满足k个，无法翻转
        next_head = next_head->next; //next_head不断移动，循环完时在下一组的头结点
    }
    list* head0 = reverse(head, next_head); //先完成一组找到第一组翻转后的头结点，也就是整个翻转后的头结点
    head->next = reverseKGroup(next_head, k); //以下一组的头结点进入递归
    return head0;
}

创作不易，希望能得到各位的三连与关注！

​​​​​​​​​​​​​​​

标签： c语言 经验分享 链表
本文转载自: https://blog.csdn.net/qq_62306969/article/details/123958349
版权归原作者 濡 白 所有， 如有侵权，请联系我们删除。
登录后发布评论

“单链表详解（两万字细节讲解，头插法尾插法，删除交换，翻转）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航