一、原地翻转

时间复杂度O(n);

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 ;
}

测试

#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;

//结构操作
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;
    p->next = node;
    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), *q;
    while (ind--) p = p->next;
    q = p->next;
    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 30
    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 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;
            case 0 : {
                printf("翻转链表\n");
                reverse(l);
            } break;
        }
        output(l), printf("\n"); //输出链表 
    }
    #undef MAX_N
    clear_list(l);
    return 0; 
}