链表

指针

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

typedef struct Node{
    int data;
    struct Node *next;
}Node, *LinkedList;

LinkedList insert(LinkedList head, Node *node, int index) {
    if (head == NULL) {
        if (index != 0) {
            return head;
        }
        head = node;
        return head;
    }
    if (index == 0) {
        node->next = head;
        head = node;
        return head;
    }
    Node *current_node = head;
    int count = 0;
    while (current_node->next != NULL && count < index - 1) {
        current_node = current_node->next;
        count++;
    }
    if (count == index - 1) {
        node->next = current_node->next;
        current_node->next = node;
    }
    return head;
}

void output(LinkedList head) {
    if (head == NULL) {
        return;
    }
    Node *current_node = head;
    while (current_node != NULL) {
        printf("%d ", current_node->data);
        current_node = current_node->next;
    }
    printf("\n");
}

LinkedList delete_node(LinkedList head, int index) {
    if (head == NULL) {
        return head;
    }
    Node *current_node = head;
    int count = 0;
    if (index == 0) {
        head = head->next;
        free(current_node);
        return head;
    }
    while (current_node->next != NULL && count < index - 1) {
        current_node = current_node->next;
        count++;
    }
    if (count == index - 1 && current_node->next != NULL) {
        Node *delete_node = current_node->next;
        current_node->next = delete_node->next;
        free(delete_node);
    }
    return head;
}

//下面实现链表的反转函数 reverse
LinkedList reverse(LinkedList head) {
    if (head == NULL) {
        return head;
    }
    Node *next_node, *current_node;
    current_node = head->next;
    head->next = NULL;
    while (current_node != NULL) {
        next_node = current_node->next;
        current_node->next = head;
        head = current_node;
        current_node = next_node;
    }
    return head;
}

void clear(LinkedList head) {
    Node *current_node = head;
    while (current_node != NULL) {
        Node *delete_node = current_node;
        current_node = current_node->next;
        free(delete_node);
    }
}

int main() {
    LinkedList linkedlist = NULL;
    for (int i = 1; i <= 10; i++) {
        Node *node = (Node *)malloc(sizeof(Node));
        node->data = i;
        node->next = NULL;
        linkedlist = insert(linkedlist, node, i - 1);
    }
    output(linkedlist);
    linkedlist = delete_node(linkedlist, 3);
    output(linkedlist);
    
    linkedlist = reverse(linkedlist);
    output(linkedlist);
    clear(linkedlist);
    return 0;
}

虚拟头节点

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

//结构定义
typedef struct Node { //节点 
    int data;
    struct Node *next;
} Node;

typedef struct List { //链表
    Node head; //定义虚拟头节点
    int length; //当前链表的长度
} List;

//链表范围[0, length) 
//结构操作 
Node *getnewNode(int val) { //节点初始化 
    //将待插入的val封装为节点 
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = val;
    node->next = NULL; 
    return node;
}

List *init_List() { //链表初始化 
    List *l = (List *)malloc(sizeof(List));
    l->head.next = NULL;
    l->length = 0;
    return l;
} 

int insert(List *l, int ind, int val) {
    if (l == NULL) return 0;
    if (l->length < ind || ind < 0) return 0;
    Node *p = &(l->head), *node = getnewNode(val);
    while (ind--) p = p->next; //找到想插入的节点的前一个节点；
    node->next = p->next; //使待插入节点的next存入待插入节点下一个节点的地址 
    p->next = node; //使待插入节点上一个节点的next存入待插入节点的地址
    l->length += 1;
    return 1;
}


void clear_Node(Node *node) { //节点销毁 
    if (node == NULL) return ;
    free(node);
}

int erase(List *l, int ind) { //删除节点 
    if (l == NULL) return 0;
    if (ind < 0 || ind >= l->length) return 0;
    Node *p = &(l->head);
    Node *q;
    while (ind--) p = p->next; //走到待删除节点的前一个位置 
    q = p->next; //q指向待删除节点 
    p->next = q->next; // 使待删除节点前一个节点指向待删除节点后一个节点； 
    clear_Node(q);
    l->length -= 1;
    return 1;
}

void clear_list(List *l) { //链表销毁 
    if (l == NULL) return ;
    Node *p = l->head.next, *q;
    while (p != NULL) {
        q = p->next;
        clear_Node(p);
        p = q;
    }
    free(l);
    return ;
}

void output(List *l) {
    if (l == NULL) return ;
    printf("链表长度%d\n", l->length);
    for (Node *p = l->head.next; p != NULL; p = p->next) {
        printf("%d->", p->data);
    }
    printf("NULL\n");
    return ;
} 

void reverse(List *l) { //原地翻转 
    if (l == NULL) return ;
    Node *p = l->head.next, *q;
    l->head.next = NULL;
    while (p != NULL) {
        q = p->next;
        p->next = l->head.next;
        l->head.next = p;
        p = q;
    }
    return ;
} 

int main() {
    srand(time(0));
    List *l = init_List();
    #define MAX_N 20
    for (int i = 0; i < MAX_N; i++) {
        int val = rand() % 100;
        int ind = rand() % (l->length + 3) - 1;
        int op = rand() % 4;
        switch(op) {
            case 0 :
            case 1 :
            case 2 : {
                printf("插入位置 %d, 插入元素 %d, %s\n", ind, val, insert(l, ind, val) ? "插入成功" : "插入失败");
            } break;
            case 3 : {
                printf("删除位置 %d, %s\n", ind, erase(l, ind) ? "删除成功": "删除失败");
            } break;
        }
        output(l), printf("\n"); //输出链表 
    }
    #undef MAX_N
    clear_list(l);
    return 0; 
}