反转双向链表问题

Question

我正在尝试翻转一个双向链表，但一直没有成功。在翻转后，该链表似乎变为空。

这是我的实现：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct Item Item;
typedef struct DLL DLL;

struct Item {
    int value;
    Item* next;
    Item* prev;
};

struct DLL {
    Item* head;
    Item* tail;
    int size;
    void(*add)(DLL*, int);
    void(*addToTail)(DLL*, int);
};

void add(DLL* list, int val) {
    Item* new_item = (Item*) malloc(sizeof(Item));
    if (new_item == NULL) {
        exit(-1);
    }
    new_item->value = val;
    new_item->next = list->head->next;
    list->head->next = new_item;
    new_item->prev = list->head;
    list->size++;
}

void addToTail(DLL* list, int val) {
    Item* new_item = (Item*) malloc(sizeof(Item));
    if (new_item == NULL) {
        exit(-1);
    }
    new_item->value = val;
    new_item->prev = list->tail->prev;
    list->tail->prev = new_item;
    new_item->next = list->tail;
    list->size++;
}

Item* find(DLL* list, int val) {
    Item* iter = list->head->next;
    while (iter != list->tail) {
        if (iter->value == val) {
            return iter;
        }
        iter = iter->next;
    }
    return NULL;
}

void reverse(DLL* list) {
    Item* current = list->head;
    Item* temp = NULL;
    while (current != NULL) {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = current->prev;
    }

    temp = list->head;
    list->head = list->tail;
    list->tail = temp;
}

void printList(DLL* list) {
    Item* iter = list->head->next;
    while (iter != list->tail) {
        printf("%d\n", iter->value);
        iter = iter->next;
    }
}

DLL* initDLL() {
    DLL* list = (DLL*) malloc(sizeof(DLL));
    if (list == NULL) {
        exit(-1);
    }

    // Creating head & tail
    list->head = (Item*) malloc(sizeof(Item));
    list->tail = (Item*) malloc(sizeof(Item));
    if (list->head == NULL || list->tail == NULL) {
        free(list);
        exit(-1);
    }

    // Initializing head & tail values just for testing
    list->head->value = 100;
    list->tail->value = 200;

    list->head->prev = NULL;
    list->head->next = list->tail;
    list->tail->prev = list->head;
    list->tail->next = NULL;

    list->size = 0;
    list->add = add;
    list->addToTail = addToTail;

    return list;
}

int main() {
    DLL* my_list = initDLL();
    my_list->add(my_list, 1);
    my_list->add(my_list, 2);
    my_list->add(my_list, 3);

    printList(my_list);
    // Outputs:
    // 3
    // 2
    // 1

    reverse(my_list);

    printList(my_list);
    // Prints nothing since list->head->next == list->tail
}

I expected

3
2
1
1
2
3

但只获取

3
2
1

第一个printList()如预期运行，但第二个没有产生任何输出。

检查问题后，我发现在反转列表后，由于某种原因list->head->next指向list->tail，即使列表中有3个元素也是如此。

我在网上搜索了一些示例，但遇到的实现并不使用类似我的DLL结构，而只使用Node结构。

- eden

---

我不明白为什么你需要反转一个DLL。你可以有一个从尾到头打印的函数。 - babon

这是为了学习目的。 - eden

编写一个函数，从尾到头遍历并显示链表，这是双向链表的反向操作。 - krpra

@melpomene，这是很多代码，但似乎没有什么可以省略的。我认为这是一个很好的问题。 - Toby Speight

请阅读并理解关于在C语言中为什么不要强制转换malloc()及其相关函数的返回值的问题（/q/605845）。例如，在此代码中，建议使用Item* new_item = malloc(sizeof *new_item);。 - Toby Speight

Answer 1

在你的添加函数中，你需要在设置`new_item->next = list->head->next;`之后将`new_item->next->prev`设置为`new_item`。

void add(DLL* list, int val) {
    Item* new_item = malloc(sizeof *new_item);
    if (new_item == NULL) {
        exit(EXIT_FAILURE);
    }
    new_item->value = val;
    new_item->next = list->head->next;
    new_item->next->prev = new_item;   // <--- This is missing in your code 
    list->head->next = new_item;
    new_item->prev = list->head;
    list->size++;
}

你的`addToTail()`中有类似的问题。你需要将`new_item->prev->next`设置为`new_item`。

- H.S.