C语言链表操作详解：初始化、插入、头插、尾插与逆转

C语言链表操作详解：初始化、插入、头插、尾插与逆转

引用

CSDN

1.

https://blog.csdn.net/qq_63456518/article/details/136635573

链表是数据结构中一种常见的线性表，其特点是通过指针将数据元素链接在一起，形成一个链状结构。链表可以分为带头节点和不带头节点两种类型，每种类型在插入、删除等操作上都有其特点。本文将通过C语言代码示例，详细介绍链表的初始化、插入、头插、尾插以及逆转等基本操作。

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

/**
 * 1、链表初始化
 * 2、插入链表
 * 3、头插链表
 * 4、打印链表（不带头节点）
 * 5、打印链表（带头结点）
 * 6、逆转链表（带头节点）
 * 7、逆转链表（不带头节点）
 */
typedef int ElementType;
typedef struct Node * PtrToNode;
struct Node{
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode List;

//初始化
void initList(List head){
    head -> Next = NULL;
}

//插入链表
_Bool insertList(List head,ElementType e,int index){
    if(index < 1) return 0;
    while(--index){
        head = head -> Next;
        if(head == NULL) return 0;
    }
    //创建一个新节点
    List list = malloc(sizeof(struct Node));
    list -> Data = e;
    list -> Next = head -> Next;
    head -> Next = list;
    return 1;
}

//头插链表
_Bool headInsertNode(List head,ElementType e){
    List newNode = malloc(sizeof(struct Node));
    if(newNode == NULL) return 0;
    newNode -> Data = e;
    newNode -> Next = head -> Next;
    head -> Next = newNode;
    return 1;
}

//尾插链表
_Bool rearInsertNode(List head,ElementType e){
    List newNode = malloc(sizeof(struct Node));
    if(newNode == NULL) return 0;
    newNode -> Data = e;
    newNode -> Next = NULL;
    while(head -> Next){
        head = head -> Next;
    }
    head -> Next = newNode;
    return 1;
}

//打印链表（不带头节点）
void Print(List head){
    while(head -> Next){
        //头节点不存放数据，从第二个开始打印
        head = head -> Next;
        printf("%d ",head -> Data);
    }
    printf("\n");
}

//打印链表2（带头结点）
void Print2(List head){
    while(head){
        printf("%d ",head -> Data);
        head = head -> Next;
    }
    printf("\n");
}

//逆转链表1
List Reverse1(List head){
    // 创建一个指针存放新的头节点
    List newHead = malloc(sizeof(struct Node));
    initList(newHead); // 初始化新链表的头节点
    head = head->Next; // 跳过头节点
    while (head) {
        List tmp = malloc(sizeof(struct Node)); // 创建一个新节点
        tmp->Data = head->Data;
        tmp->Next = newHead->Next;
        newHead->Next = tmp;
        head = head->Next;
    }
    return newHead;
}

//逆转链表2
List Reverse2(List head){
    struct Node * newHead = NULL,*tmp;
    head = head -> Next;
    while(head != NULL){
        tmp = head;
        head = head -> Next;
        tmp -> Next = newHead;
        newHead = tmp;
    }
    return newHead;
}

int main(){
    struct Node L1;
    initList(&L1);
    for(int i = 0; i < 10; i++){
        insertList(&L1,(i+1)*10,i+1);
    }
    List L21,L22;
    L21 = Reverse1(&L1);
    L22 = Reverse2(&L1);
    printf("初始链表：");
    Print(&L1);
    printf("逆转链表法1：打印逆转链表：");
    Print(L21);
    printf("逆转链表法2：打印逆转链表：");
    Print2(L22);

    //头插法插入链表
    struct Node L3;
    initList(&L3);
    for(int i = 0; i < 10;i++){
        headInsertNode(&L3,(i+1)*10);
    }
    //打印L3链表
    printf("打印头插链表：");
    Print(&L3);
    headInsertNode(&L3,999);
    printf("打印变化后的链表：");
    Print(&L3);

    //尾插发插入链表
    struct Node L4;
    initList(&L4);
    for(int i = 0; i < 10;i++){
        rearInsertNode(&L4,(i+1)*10);
    }
    printf("打印尾插链表：");
    Print(&L4);
    rearInsertNode(&L4,999);
    printf("打印变化后的链表：");
    Print(&L4);

    //向链表输入n个数，然后头插链表L4，并打印出来该链表
    int n;
    printf("请输入n：\n");
    scanf("%d",&n);
    ElementType m;
    printf("请输入n个数：\n");
    for(int i = 0; i < n;i++){
        scanf("%d",&m);
        headInsertNode(&L4,m);
    }
    Print(&L4);

    //向链表输入k个数，然后尾插链表L4，并打印出来该链表
    int k;
    printf("请输入k：\n");
    scanf("%d",&k);
    ElementType x;
    printf("请输入k个数：\n");
    for(int i = 0;i < k;i++){
        scanf("%d",&x);
        rearInsertNode(&L4,x);
    }
    Print(&L4);
    return 0;
}

此外，还提供了一个简化的链表逆转函数：

List Reverse(List L) {
    struct Node * newList = NULL,*tmp;
    while(L != NULL){
        tmp = L;
        L = L -> Next;
        tmp -> Next = newList;
        newList = tmp;
    }
    return newList;
}