单链表的常见操作

含头结点的单链表

//链表的定义
struct Node
{
    int data;
    struct Node *next;
} ;

//尾插法创建链表
struct Node *create_list_R()
{
    struct Node *head = (struct Node *)malloc(sizeof(struct Node));
    struct Node *p = head, *q = NULL;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        q = (struct Node *)malloc(sizeof(struct Node));
        scanf("%d", &q->data);
        q->next = NULL;
        p->next = q;
        p = q;
    }
    return head;
}

//头插法创建链表
struct Node *create_list_H()
{
    struct Node *head = (struct Node *)malloc(sizeof(struct Node));
    struct Node *p = head;
    head->next = NULL;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        p = (struct Node *)malloc(sizeof(struct Node));
        scanf("%d", &p->data);
        p->next = head->next;
        head->next = p;
    }
    return head;
}


//输出链表
void print_list(struct Node *head)
{
    for (struct Node *p = head->next; p != NULL; p = p->next)
        printf("%d\t", p->data);
    printf("\n");
}

//插入结点（序号从1开始）
struct Node *insert_node(struct Node *head, int data, int index)
{
    struct Node *p = head, *q = (struct Node *)malloc(sizeof(struct Node));
    for (int i = 1; i < index; ++i, p = p->next)
        ;
    if (p == NULL || index <= 0)
        return NULL;
    q->data = data;
    q->next = p->next;
    p->next = q;
    return q;
}

//删除结点（序号从1开始）
void delete_node(struct Node *head, int index)
{
    struct Node *p = NULL, *q = head->next;
    for (int i = 1; i < index; ++i)
    {
        p = q;
        q = q->next;
    }
    p->next = q->next;
    free(q);
}

//搜索结点（序号从1开始）
int search_node(struct Node *head, int data)
{
    int index = 1;
    for (struct Node *p = head->next; p != NULL; p = p->next, ++index)
    {
        if (p->data == data)
            return index;
    }
    return -1;
}

//反转链表
struct Node *reverse_list(struct Node *head)
{
    struct Node *cur = head->next, *prev = NULL, *next = NULL;
    while (cur != NULL)
    {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    head->next = prev;
    return head;
}

//求链表长度
int list_length(struct Node *head)
{
    struct Node *p = head->next;
    int i;
    for (i = 0; p != NULL; p = p->next, ++i)
        ;
    return i;
}

//链表冒泡排序
struct Node *bubblesort_list(struct Node *head)
{
    struct Node *p = NULL;
    int len = list_length(head), i, j, temp;
    for (i = 0; i < len - 1; ++i)
    {
        p = head->next;
        for (j = 0; j < len - i - 1; ++j)
        {
            if (p->data > p->next->data)
            {
                temp = p->data;
                p->data = p->next->data;
                p->next->data = temp;
            }
            p = p->next;
        }
    }
    return head;
}

不含头结点的单链表

//链表的定义
struct Node
{
    int data;
    struct Node *next;
};

//尾插法创建链表
struct Node *create_list_R()
{
    struct Node *head = NULL, *p = head, *q = NULL;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        q = (struct Node *)malloc(sizeof(struct Node));
        scanf("%d", &q->data);
        q->next = NULL;
        if (i == 0)
            head = q;
        else
            p->next = q;
        p = q;
    }
    return head;
}

//头插法创建链表
struct Node *create_list_H()
{
    struct Node *head = NULL, *p = NULL;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        p = (struct Node *)malloc(sizeof(struct Node));
        scanf("%d", &p->data);
        if (i == 0)
        {
            head = p;
            p->next = NULL;
        }
        else
        {
            p->next = head;
            head = p;
        }
    }
    return head;
}

//输出链表
void print_list(struct Node *head)
{
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d\t", p->data);
    printf("\n");
}

//插入结点（序号从1开始）
struct Node *insert_node(struct Node *head, int data, int index)
{
    struct Node *p = head, *q = NULL;
    for (int i = 1; i < index - 1 && p != NULL; ++i, p = p->next)
        ;
    if (p == NULL || index <= 0)
        return NULL;
    q = (struct Node *)malloc(sizeof(struct Node));
    q->data = data;
    if (index == 1)
    {
        q->next = head;
        head = q;
    }
    else
    {
        q->next = p->next;
        p->next = q;
    }
    return q;
}

//删除结点（序号从1开始）
void delete_node(struct Node **head, int index)
{
    struct Node *p = *head, *q = NULL;
    for (int i = 1; i < index && p != NULL; ++i)
    {
        q = p;
        p = p->next;
    }
    if (p == NULL || index <= 0)
        return;
    if (index == 1)
        *head = p->next;
    else
        q->next = p->next;
    free(p);
}

//搜索结点（序号从1开始）
int search_node(struct Node *head, int data)
{
    int i;
    struct Node *p = head;
    for (i = 1; p != NULL; p = p->next, ++i)
        if (p->data == data)
            return i;
    return -1;
}

//反转链表
struct Node *reverse_list(struct Node *head)
{
    struct Node *cur = head, *prev = NULL, *next = NULL;
    while (cur != NULL)
    {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    head = prev;
    return head;
}

//求链表长度
int list_length(struct Node *head)
{
    int i;
    struct Node *p = head;
    for (i = 0; p != NULL; ++i, p = p->next)
        ;
    return i;
}

//链表冒泡排序
struct Node *bubblesort_list(struct Node *head)
{
    int len = list_length(head), temp;
    struct Node *p;
    for (int i = 0; i < len - 1; ++i)
    {
        p = head;
        for (int j = 0; j < len - i - 1; ++j)
        {
            if (p->data > p->next->data)
            {
                temp = p->data;
                p->data = p->next->data;
                p->next->data = temp;
            }
            p = p->next;
        }
    }
    return head;
}