将单链表转为双向链表（C语言）：实现反向遍历遇阻求助

1. 定义双向链表节点结构 #

把单链表节点扩展为双向链表节点，新增prev指针用于指向前驱节点：

typedef struct Node {
    int data;
    struct Node* next;  // 指向后继节点
    struct Node* prev;  // 指向前驱节点
} Node;

2. 构建双向链表的指针处理逻辑 #

以尾部插入节点为例，需要同时维护next和prev的指向关系：

• 若链表为空，新节点作为头节点，prev和next都设为NULL
• 若链表非空，找到尾节点后：
  • 尾节点的next指向新节点
  • 新节点的prev指向尾节点
  • 新节点的next设为NULL

尾部插入代码示例：

Node* addNode(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) {
        newNode->prev = NULL;
        return newNode;
    }

    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
    return head;
}

3. 正向遍历函数（原display） #

和单链表逻辑一致，从头节点沿next遍历至NULL：

void display(Node* head) {
    Node* temp = head;
    printf("正向遍历：");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

4. 反向遍历函数（displayReverse实现） #

先找到链表尾节点，再沿prev指针向前遍历至NULL：

void displayReverse(Node* head) {
    if (head == NULL) {
        printf("链表为空\n");
        return;
    }

    // 定位到尾节点
    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    printf("反向遍历：");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->prev;
    }
    printf("\n");
}

5. 完整测试示例 #

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

typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

Node* addNode(Node* head, int data);
void display(Node* head);
void displayReverse(Node* head);

int main() {
    Node* head = NULL;
    head = addNode(head, 10);
    head = addNode(head, 20);
    head = addNode(head, 30);
    head = addNode(head, 40);

    display(head);
    displayReverse(head);

    // 实际使用需添加内存释放逻辑，示例省略
    return 0;
}

// 尾部插入节点
Node* addNode(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) {
        newNode->prev = NULL;
        return newNode;
    }

    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
    return head;
}

// 正向遍历
void display(Node* head) {
    Node* temp = head;
    printf("正向遍历：");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// 反向遍历
void displayReverse(Node* head) {
    if (head == NULL) {
        printf("链表为空\n");
        return;
    }

    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    printf("反向遍历：");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->prev;
    }
    printf("\n");
}

运行输出：

正向遍历：10 20 30 40 
反向遍历：40 30 20 10 

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