C语言编写一个链表

以下是C语言编写一个链表的完整攻略：

概述

链表是一种基本数据结构，它是由一系列不连续的节点组成的。每个节点包含两部分，一部分是数据，一部分是指向下一个节点的指针。链表中的数据可以是任何类型的，如int、char、结构体等。链表有单向链表和双向链表两种类型，本文主要介绍单向链表。

相关操作

链表的基本操作包括插入、删除、查找等。下面介绍单向链表的几个基本操作：

链表节点的定义

typedef struct _ListNode
{
    int val;
    struct _ListNode* next;
}ListNode;

链表节点包含两部分，一部分是节点的值，另一部分是指向下一个节点的指针。

在链表头插入一个节点

ListNode* addAtHead(ListNode* head, int val)
{
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = head;
    return newNode;
}

上述函数实现在链表头插入一个节点。

在链表尾插入一个节点

ListNode* addAtTail(ListNode* head, int val)
{
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL; 

    if (head == NULL) return newNode;

    ListNode* cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
    return head;
}

上述函数实现在链表尾插入一个节点。

删除链表中第一个值为给定值的节点

ListNode* deleteNode(ListNode* head, int val)
{
    if (head == NULL) return NULL;
    if (head->val == val) return head->next;

    ListNode* cur = head;
    while (cur->next != NULL && cur->next->val != val) {
        cur = cur->next;
    }
    if (cur->next != NULL) {
        cur->next = cur->next->next;
    }
    return head;
}

上述函数实现删除链表中第一个值为给定值的节点。

示例

下面给出两个示例：

示例1

输入：head = [1,2,3,4,5], val = 3
输出：[1,2,4,5]

ListNode* head = NULL;
head = addAtTail(head, 1);
head = addAtTail(head, 2);
head = addAtTail(head, 3);
head = addAtTail(head, 4);
head = addAtTail(head, 5);

printList(head);
head = deleteNode(head, 3);
printList(head);

示例2

输入：head = [1,2,3,4,5], val = 6
输出：[1,2,3,4,5]

ListNode* head = NULL;
head = addAtTail(head, 1);
head = addAtTail(head, 2);
head = addAtTail(head, 3);
head = addAtTail(head, 4);
head = addAtTail(head, 5);

printList(head);
head = deleteNode(head, 6);
printList(head);

总结

本文介绍了C语言编写一个链表的基本操作，包括链表节点的定义、在链表头插入一个节点、在链表尾插入一个节点、删除链表中第一个值为给定值的节点等。同时给出了两个示例。