C语言数据结构：链表的操作实现

本文包括链表的基本操作：初始化、头插法、尾插法、遍历打印、获取尾结点地址、指定位置添加和删除结点、获取链表长度、得到尾指针、释放链表、获得倒数第K个结点的值（快慢指针法）、翻转链表。

在链表的学习中（个人觉得）我们需要注意的几点：

1、结点类型声明的格式，指针域不可以使用别名取声明，

2、指针域的熟悉，要懂得L->next的含义，看到后知道其内容是什么意思。

3、循环的临界条件判断，需要多次写代码去熟悉。

4、多学习技巧，去降低时间复杂度，如快慢指针。

快慢指针用法（后续还会补充）：

1.找到倒数第K个值：快指针先走K步，循环向链表尾部走，直到指向NULL，这时慢指针就会指向想要的结点。

2、寻找链表的中点（也可以找到其他比例的点去分割链表）：快指针一次向尾部走两步，慢指针走一步，直到指向NULL，这时慢指针就会指向中间结点（偶数链表会指向中间的上一个，奇数会指向中间值）。

3.链表是否循环：通过快2步慢1步的方法、判断地址是否有重复的地方。

#include <stdio.h>
#include <stdlib.h>
typedef int Elemtype;
// 正确认识 typedef的重要性， 如果需要把成千上万的int 改为double 会有很大工作量，
// 可以事先在表头定义typedef int i，修改时只需要把int 改为double
typedef struct node
{
    Elemtype data;     // 数据域
    struct node *next; // 指针域
} Node;
Node *Node_init();                                 // 链表初始化 分配空间
void insertHead(Node *L, Elemtype e);              // 头插法
void listNode(Node *L);                            // 遍历链表(应该使用一个临时指针来遍历链表，而不是修改传入的头节点指针 L)
Node *get_tail(Node *L);                           // 获取尾结点的地址
Node *insertTail(Node *tail, Elemtype e);          // 在尾结点后插入一个数据
int insertNode(Node *L, int location, Elemtype e); // 在特定位置插入数据
int deletNode(Node *L, int location);              // 删除特定位置结点
int getlength(Node *L);                            // 获取链表长度
void freeList(Node *L);                            // 释放链表
int findNode(Node *L, Elemtype k);                 // 找到倒数第K个值
Node *reverslist(Node *L);                         // 翻转链表
Node *head;                                        // 定义头指针 在init初始化函数中对头指针分配空间
int main(int argc, char const *argv[])
{
    head = Node_init();  // 带头节点  链表初始化
    insertHead(head, 3); // 头插法
    insertHead(head, 2);
    insertHead(head, 1);
    Node *tail = get_tail(head); // 得到尾指针
    tail = insertTail(tail, 4);  // 尾插法 返回新的尾指针
    tail = insertTail(tail, 5);
    insertTail(tail, 6);   // 尾指针不变动
    listNode(head);        // 遍历链表
    Node *hd;              // 创建新的指针
    hd = reverslist(head); // 翻转链表
    listNode(hd);          // 遍历链表

    return 0;
}
Node *Node_init()
{
    Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配空间
    head->data = 0;                            // 初始化值为0
    head->next = NULL;                         // 初始化的指针为空
    return head;                               // 返回头指针
}
void insertHead(Node *L, Elemtype e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 要插入的结点分配空间
    p->next = L->next;                      // 新结点指向原头结点
    p->data = e;                            // 新结点赋值
    L->next = p;                            // 头指针指向新头结点
}
void listNode(Node *L)
{
    Node *p = L->next; // 因为头指针只能指向头结点，所以需要新的指针来遍历数组
    while (p != NULL)  // 尾结点的指针与为空，所以可以作为循环的条件
    {
        printf("%d ", p->data); // 打印新的指针指向的数据与
        p = p->next;            // 指针指向下一个结点
    }
    printf("\n");
}
Node *get_tail(Node *L)
{
    Node *p = L;            // 因为头指针只能指向头结点，所以需要新的指针来遍历数组
    while (p->next != NULL) // 尾结点的指针与为空，所以可以作为循环的条件 直到指向尾结点
    {
        p = p->next;
    }
    return p;
}
Node *insertTail(Node *tail, Elemtype e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 为新的尾结点分配空间
    tail->next = p;                         // 原尾结点指向新的尾结点，衔接
    p->data = e;                            // 新结点数据与赋值
    p->next = NULL;                         // 新尾结点指向空
    return p;
}
int insertNode(Node *L, int location, Elemtype e)
{
    Node *p = (Node *)malloc(sizeof(Node)); // 为新的结点分配空间
    for (int i = 0; i < location - 1; i++)  // 循环location-1次到达目标前一个位置，然后进行插入
    {
        L = L->next;
        if (L == NULL)
        {
            return 0;
        }
    }
    p->next = L->next;
    p->data = e;
    L->next = p;
}
int deletNode(Node *L, int location)
{
    Node *p = L;                           // 创建q指针，最后指向要被删除的结点
    for (int i = 0; i < location - 1; i++) // 循环location-1次到达目标前一个位置，然后进行删除
    {
        p = p->next;
        if (p->next == NULL) // 判断下一个结点（要被删除的结点）是否为空
        {
            printf("要删除的位置错误");
            return 1;
        }
    }
    Node *q = p->next; // q指向被删除的结点
    p->next = q->next; // p指向下一个结点，将q从链表中断开
    free(q);           // 释放删除结点的空间
    return 0;
}
int getlength(Node *L)
{
    Node *p = L;
    int count = 0;
    while (p != NULL) // 让计数器跟随指针自增，直到尾结点
    {
        p = p->next;
        count++;
    }
    return count; // 返回长度
}
void freeList(Node *L)
{
    Node *p = L->next;      // 定义p指针 指向头结点
    Node *q;                // 定义q指针
    while (p->next != NULL) // 检查是否到尾结点
    {
        q = p->next; // q指针指向p的下一个结点
        free(p);     // 释放p指向结点的内存
        p = q;       // p追随q
    }
    L->next = NULL; // 清空链表后，使头指针指向空
}
int findNode(Node *L, Elemtype k)
{
    Node *f = L->next; // 快指针
    Node *s = L->next; // 慢指针
    int len = 0;
    if (k > (len = getlength(head)))
    {
        printf("输入值不合法");
    }
    else
    {
        for (int i = 0; i < k; i++) // 让快指针先走k步
        {
            f = f->next;
        }
        while (f->next != NULL) // 当快指针指向末尾，慢指针所指就是倒数第K个结点
        {
            f = f->next;
            s = s->next;
        }
        printf("%d \n", s->data); // 打印倒数K结点的值
    }
    return 0;
}
Node *reverslist(Node *L)
{                           // 定义三个指针，使链表的指针方向翻转，达到翻转链表的目的
    Node *first = NULL;     // 1指针先作为新链表的尾指针指向空
    Node *second = L->next; // 2指针指向头结点
    Node *third;
    while (second != NULL) // 最后1指针指向原尾结点
    {
        third = second->next; // 3指针指向2的下一个结点
        second->next = first; // 2所指向的结点的指针域指1，翻转指针的指向
        first = second;       // 1 2两个指针下移
        second = third;
    }
    Node *hd = Node_init(); // 新建链表头指针，并初始化
    hd->next = first;       // 新指针指向新的头结点

    return hd; // 返回新链表的头指针
}

推荐某站孙老师的课程：（有详细的C语言代码，不是伪代码！！！）《数据结构（C 语言描述）》也许是全站最良心最通俗易懂最好看的数据结构课（最迟每周五更新~~）_哔哩哔哩_bilibili