我在反转双向链表时遇到问题

Question

我正在学习链表，正在做一道题，要求你反转双向链表。我的代码工作得很好，但我不明白如何。除了

reverse_list

函数之外，你可以忽略整个事情。正如您所看到的，在

while

循环中，条件是

ptr->next != NULL

。这种情况不应该让我到达最后一个节点，直到最后一个操作

ptr = ptr->prev

，这意味着在最后一个节点中不应该执行该

while

循环内的其他操作。

按照这个逻辑，

ptr->prev

必须仍然指向倒数第二个节点（或者你可以说反转后的第二个节点），而它应该是

NULL

。我不明白为什么即使没有正确反转，它也给出了正确的答案。

// reverse a double linked list
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    struct node *prev;
    int data;
    struct node *next;
} st;

void print(st *head)
{
    while (head)
    {
        printf("%d ", head->data);
        head = head->next;
    }
}

void add_node(st *head, int data)
{
    st *ptr = malloc(sizeof(st));
    ptr->data = data;
    ptr->next = NULL;
    while (head->next)
    {
        head = head->next;
    }
    head->next = ptr;
}

st *reverse_list(st *head)
{
    st *ptr = head->next;
    head->next = NULL;
    while (ptr->next != NULL)
    {
        head->prev = ptr;
        ptr->prev  =ptr->next;
        ptr->next = head;
        head = ptr;
        ptr = ptr->prev;
    }
    ptr->next = head;;
    head = ptr;
    return head;
}

int main()
{
    st *head = malloc(sizeof(st));
    head->prev = NULL;
    head->data = 12;
    head->next = NULL;

    add_node(head, 22);
    add_node(head, 1);
    add_node(head, 24);
    add_node(head, 45);

    printf("before reverse\n");
    print(head);

    head = reverse_list(head);
    printf("\nafter reverse\n");
    print(head);

    return 0;
}

// here is the output

before reverse
12 22 1 24 45 
after reverse
45 24 1 22 12 

Answer 1

存在多个问题：

• void add_node(st *head, int data)

  无法正确构造双向链表：它应该采用指向调用者作用域中

  head

  指针的指针（特殊情况下是第一个节点），并将

  ptr->next

  设置为指向列表中的前一个节点.

如果列表为空 (
• reverse_list

  ) 或只有单个元素 (

  head == NULL

  )，则

  head->next == NULL

  具有未定义的行为。

• print

  函数沿着

  next

  指针迭代，但它不检查

  prev

  指针是否正确。该程序为简单的 4 元素测试用例生成了预期的输出，但构建的列表及其反向版本中的

  prev

  链接都是不正确的。