编辑代码

#include <stdio.h>
#include <stdlib.h>
typedef struct Link {
    int elem;
    struct Link* next;
}link;
//无头结点链表{1,2,3,4}初始化
link* initLink() {
    //创建头指针
    link* p = NULL;
    //创建首元结点
    link* temp = (link*)malloc(sizeof(link));
    temp->elem = 1;
    temp->next = NULL;
    p = temp;
    for (int i = 2; i < 5; i++) {
        link* a = (link*)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;
}
// 展示链表
void display(link* p) {
    link* t = p;
    while (t) {
        printf("%d ", t->elem);
        t = t->next;
    }
    printf("\n");
}
// 迭代反转链表
link* interation_reverse(link* p) {
    if (p == NULL || p->next == NULL) {
        return p;
    }
    else {
        link* beg = NULL;
        link* mid = p;
        link* end = p->next;
        //一直遍历
        while (1) {
            //修改mid所指节点的指向
            mid->next = beg;
            //此时判断end是否为NULL, 如果成立则退出循环
            if (end == NULL) {
                break;
            }
            //整体向后移动3个指针
            beg = mid;
            mid = end;
            end = end->next;
        }
        //最后修改头指针的指向
        p = mid;
        return p;
    }

}
//递归反转链表
link* recursive_reverse(link* head) {
    //递归的出口
    if (head == NULL || head->next == NULL) {
        return head;
    }
    else {
        //一直递归，找到链表中最后一个节点
        link* new_head = recursive_reverse(head->next);
        head->next->next = head;
        head->next = NULL;
        return new_head;

    }
}
//头插法（开辟新空间）反转链表
link* head_reveres(link* head) {
    link* new_head = NULL;
    link* temp = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    while (head != NULL) {
        temp = head;
        //将temp从head中摘除
        head = head->next;
        //将temp插入到new_head的头部
        temp->next = new_head;
        new_head = temp;
    }
    return new_head;
}
//就地逆置发反转链表
link* local_reverse(link* head) {
    link *beg = NULL;
    link* end = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    beg = head;
    end = head->next;
    while (end != NULL)
    {
        //将end从链表中摘除
        beg->next = end->next;
        //将end移动至链表头
        end->next = head;
        head = end;
        //调整end的指向
        end = beg->next;
    }
    return head;
}
int main() {
    link* p = initLink();
    display(p);
    //p = interation_reverse(p);
    //display(p);
    //p = recursive_reverse(p);
    p = local_reverse(p);
    display(p);
    return 0;
}