递归双向链表反转函数异常终止问题排查及传参正确性咨询

问题背景 #

编写递归函数实现双向链表反转，代码未完成，程序执行中途退出，相关代码、运行输出及疑问如下：

代码 #

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

typedef struct nodes
{
    uint8_t x;
    struct nodes *next;
    struct nodes *prev;
}Node;

Node *head = NULL;

void rev_rec_dll(Node **a, Node **b)
{
        //check if it is last node in the list
    if((*a)->next != NULL)
    {
                //set next to prev and prev to next
        (*a)->next = (*a)->prev;
        (*a)->prev = (*b);
        printf("done for node %d and moving on..\n", ((*a)->x));
        //recursive call by passing next two nodes
                rev_rec_dll(b, &((*b)->next));
    }
    else
    {
        printf("reached new head\r\n");
        head = (*a);
    }
}

void add_node(Node **h_node, uint8_t x)
{
        //check if there is at least one node in the list and if not add first node
    if((*h_node) == NULL)
    {
        *h_node = (Node *)malloc(sizeof(Node));
        (*h_node)->x    = x;
        (*h_node)->next = NULL;
        (*h_node)->prev = NULL;
    }
    else
    {
        Node *temp = *h_node;
        //get the last node
        while(temp->next != NULL)
        {
            temp = temp->next;
        }
        //add new node
        Node *newNode = (Node *)malloc(sizeof(Node));
        
        newNode->x      = x;
        newNode->next   = NULL;
        newNode->prev   = temp;
        
        temp->next      = newNode;
    }
}

void display_nodes(Node *h_node)
{
    while(h_node != NULL)
    {
        printf("Node: %u\n", h_node->x);
        h_node = h_node->next;
    }
}

int main(int argc, char **argv)
{
        //add three nodes
    add_node(&head, 1);
    add_node(&head, 2);
    add_node(&head, 3);

    //display nodes
    display_nodes(head);

        //add three more nodes
    add_node(&head, 4);
    add_node(&head, 5);
    add_node(&head, 6);

        //display all 6 nodes
    display_nodes(head);
    
        //reverse the linked list
    rev_rec_dll(&head, &(head->next));

        //display reversed nodes 
    display_nodes(head);
    
    return 0;
}

运行输出 #

Node: 1
Node: 2
Node: 3
Node: 1
Node: 2
Node: 3
Node: 4
Node: 5
Node: 6
done for node 1 and moving on..

疑问解答 #

1. rev_rec_dll()函数存在的问题 #

• 递归逻辑混乱：修改当前节点指针后，后续递归的参数引用的是已被修改的指针，导致节点跟踪错误；最后一个节点的指针反转未完成，也没有处理新头节点与后续节点的链接。
• 边界处理缺失：未判断输入指针是否为空，若链表为空或只有一个节点，会直接触发空指针解引用；递归终止时仅设置新头节点，未完成整个链表的闭环调整。
• 指针修改顺序错误：先修改当前节点的next指针，导致后续无法正确获取原本的下一个节点，破坏了递归的节点链跟踪。

2. 传入函数的参数是否正确 #

不正确。
原因：第一次调用传入的&head和&(head->next)，在函数内部修改(*a)->next为(*a)->prev（即NULL）后，后续递归传入的&((*b)->next)会随着节点指针的修改指向错误地址。参数设计逻辑错误，应该传递当前节点的原始下一个节点引用，而非动态变化的指针地址，否则会导致递归过程中节点链断裂，访问非法内存。

3. 程序中途退出的原因 #

是内存违规（空指针解引用或非法内存访问）导致的。
具体来说：递归过程中，当处理到某个节点时，(*b)可能变为NULL（比如链表末尾的下一个节点），此时解引用(*b)->next会触发空指针异常；另外，节点指针被错误修改后，后续递归访问的内存地址已失效，触发内存访问违规，导致程序直接崩溃退出。

内容的提问来源于stack exchange，提问作者Karna