单向链表反转

最近更新于 2024-05-05 14:19

情景

初始链表

反转后

测试环境

gcc 9.4.0 – 64位

编译参数：

-no-pie -std=c17 -Wall -Werror=return-type -Werror=address -Werror=sequence-point -Werror=format-security -Wextra -pedantic -Wimplicit-fallthrough -Wsequence-point -Wswitch-unreachable -Wswitch-enum -Wstringop-truncation -Wbool-compare -Wtautological-compare -Wfloat-equal -Wshadow=global -Wpointer-arith -Wpointer-compare -Wcast-align -Wcast-qual -Wwrite-strings -Wdangling-else -Wlogical-op -Wconversion -g -O0

注：

按照 C17 标准编译

禁用了编译优化

启用了调试

初始化

调用 init() 会创建一条十个节点的链表，依次存储 0～9，创建的链表名为 head（全局变量）。调用 show_node() 可以查看 head 链表中的数据。

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


typedef struct ListNode
{
    int val;
    void *next;
} ListNode;


#define N   10  // 创建链表长度，默认 10 即为 0～9
ListNode *head = NULL;  // 全局链表


/**
 * @brief 添加节点
 * 
 * @param prev 上一个节点的地址，在其基础上添加新节点；传 NULL，则是创建独立的节点，如头部
 * @param val 节点要插入的值
 * @return ListNode* 返回新建节点的地址
 */
ListNode *add_node(ListNode *prev, int val)
{
    ListNode *new_node = (ListNode *) malloc(sizeof(ListNode));
    new_node->val = val;
    new_node->next = NULL;
    if (prev != NULL)
    {
        prev->next = new_node;
    }
    return new_node;
}


/**
 * @brief 显示链表内容
 */
void show_node()
{
    ListNode *ptr = head;
    while (1)
    {
        printf("%d ", ptr->val);
        ptr = ptr->next;
        if (ptr == NULL)
        {
            break;
        }
    }
    printf("\n");
}


/**
 * @brief 初始化链表
 *      共十个节点，依次存入 0～9
 * 
 */
void init()
{
    head = add_node(NULL, 0);
    ListNode *node_ptr = head;
    for (int i = 1; i < N; ++i)
    {
        node_ptr = add_node(node_ptr, i);
    }
}

实现一：迭代

    ListNode *last = NULL;
    ListNode *curr = NULL;
    ListNode *next = head;

    while (1)
    {
        last = curr;
        curr = next;
        next = next->next;
        curr->next = last;

        if (next == NULL)
        {
            head = curr;
            break;
        }
    }

然后为了测试一下效率（数据量大，结果更为稳定），将链表长度的 N 值改为了一千万，并注释了 show_node() 调用，因为在数据量比较大的情况下，调用两千万次 printf（原链表和逆序后的链表）消耗的时间着实不少，而这个并不是算法本身需要消耗的时间。

测试结果也显现出来了，调用了 show_node() 的情况下使用了 25 秒左右的时间，注释后算法本身逆序只用了三百多毫秒。

实现二：递归

大体上和迭代相差不大，只是前一种使用的循环，这个是用的函数递归。

// 调用格式：
//    head = recursion(NULL, head)
//    返回值 head 即为逆序后的头节点
ListNode *recursion(ListNode *prev, ListNode *curr);

ListNode *recursion(ListNode *prev, ListNode *curr)
{
    if (curr == NULL)
    {
        return prev;
    }
    ListNode *next = curr->next;
    curr->next = prev;
    return recursion(curr, next);
}

递归相比迭代循环代码简洁一点，但是因为进程的栈空间有限，函数递归调用，层数不能太多，我电脑上测试了下链表节点数大概在17万到18万之间有个界限，超过之后运行就会出现段错误。

而且对比一下时间，17万个节点耗时就有40毫秒左右，前面迭代一千万个节点耗时也才三百多毫秒，相比而言还是迭代效率更高，而且支持更高的节点数。