C语言链表反转的四种方法

//
// Created by Administrator on 2024/10/29.
//

#ifndef LINK_H
#define LINK_H
/**
 * 链表的结构体
 */
typedef struct Link {
    int element;
    struct Link *next;
} link;
#endif //LINK_H

//
// 四种链表反转算法
// Created by Administrator on 2024/10/29.
//

#pragma once
#include "Link.h"
#ifndef REVERSELIST_H
#define REVERSELIST_H


/**
 * 1. 迭代反转链表
 * @param p 初始链表
 * @return 反转后的链表
 */
link *iterationReverseLink(link *p);

/**
 * 2. 递归反转链表
 * @param p 初始链表
 * @return 反转后的链表
 */
link *recursiveReverseLink(link *p);

/**
 * 3. 头插法反转链表
 * @param p 初始链表
 * @return 反转后的链表
 */
link *headReverseLink(link *p);

/**
 * 4. 就地逆置法反转链表
 * @param p 
 * @return 
 */
link *localReverseLink(link *p);
#endif //REVERSELIST_H

//
// Created by Administrator on 2024/10/29.
//
#include "ReverseLink.h"

#include <malloc.h>
#include <stddef.h>
/**
 * 1. 迭代反转链表
 * @param p 初始链表
 * @return 反转后的链表
 */
link *iterationReverseLink(link *p) {
    /*链表为NULL或链表只有一个节点，直接返回*/
    if (p == NULL || p->next == NULL) return p;
    link *beg = NULL;
    link *mid = p;
    link *end = p->next;

    while (1) {
        mid->next = beg;
        if (end == NULL) {
            break;
        }
        /*向后移动指针*/
        beg = mid;
        mid = end;
        end = end->next;
    }
    p = mid;
    return p;
}

/**
 * 2. 递归反转链表
 * @param p 初始链表
 * @return 反转后的链表
 */
link *recursiveReverseLink(link *p) {
    /*链表为NULL或链表只有一个节点，直接返回*/
    if (p == NULL || p->next == NULL) return p;
    /*一直递归，找到链表中最后一个节点*/
    link *newP = recursiveReverseLink(p->next);
    p->next->next = p;
    p->next = NULL;
    return newP;
}

/**
 * 3. 头插法反转链表
 * @param p 初始链表
 * @return 反转后的链表
 */
link *headReverseLink(link *p) {
    /*链表为NULL或链表只有一个节点，直接返回*/
    if (p == NULL || p->next == NULL) return p;
    link *newP = NULL;
    link *temp = NULL;
    while (p != NULL) {
        temp = p;
        p = p->next;
        temp->next = newP;
        newP = temp;
    }
    return newP;
}

/**
 * 4. 就地逆置法反转链表
 * @param p
 * @return
 */
link *localReverseLink(link *p) {
    /*链表为NULL或链表只有一个节点，直接返回*/
    if (p == NULL || p->next == NULL) return p;
    link *begin = NULL;
    link *end = NULL;
    begin = p;
    end = p->next;
    while (end != NULL) {
        begin->next = end->next;
        end->next = p;
        p = end;
        end = begin->next;
    }
    return p;
}