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

发布于12月11日

我正在学习链表，并正在做一道题，要求你反转一个双向链表.我的代码运行得很好，但我不知道是怎么回事.您可以忽略除reverse_list函数以外的所有内容.如您所见，在while循环中，条件是ptr->next != NULL.这种情况应该不会让我到达最后一个 node ，直到最后一个操作ptr = ptr->prev，这意味着在最后一个 node 中不应该执行while循环中的其他操作.

这样，逻辑ptr->prev必须仍然指向倒数第二个 node (或者您可以在反转后指向第二个 node )，而它应该是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

#include <stdio.h> #include <stdlib.h> typedef struct node { struct node *prev; struct node *next; int data; } st; void print(const char *msg, const st *head) { printf("%s", msg); while (head) { printf(" %d", head->data); head = head->next; } printf("\n"); } st *add_node(st **headp, int data) { st *ptr = malloc(sizeof(st)); if (ptr == NULL) return NULL; ptr->data = data; ptr->prev = NULL; ptr->next = NULL; if (*headp == NULL) { return *headp = ptr; } else { st *last = *headp; while (last->next) { last = last->next; } ptr->prev = last; return last->next = ptr; } } st *reverse_list(st *head) { // iterate on the list, swapping the next and prev links for (st *node = head; node; node = node->prev) { st *next = node->next; node->next = node->prev; node->prev = next; head = node; } return head; } void free_list(st **headp) { for (st *node = *headp; node;) { st *next = node->next; free(node); node = next; } *headp = NULL; } int main(void) { st *head = NULL; add_node(&head, 12); add_node(&head, 22); add_node(&head, 1); add_node(&head, 24); add_node(&head, 45); print("before reverse: ", head); head = reverse_list(head); print("after reverse: ", head); free_list(&head); return 0; }

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

推荐答案

C++相关问答推荐

exit(EXIT_FAILURE)：Tcl C API类似功能

如何正确地索引C中的 struct 指针数组？

C中是否有语法可以直接初始化一个常量文本常量数组的 struct 成员？

特定闪存扇区的内存别名

#If指令中未定义宏？

以下声明和定义之间的区别

当输入负数时，排序算法存在问题

CSAPP微型shell 实验室：卡在sigprocmask

VS代码'；S C/C++扩展称C23真关键字和假关键字未定义

实现简单字典时C语言中的段错误

CGO：如何防止在使用CGO在包中包含C头文件时出现多个定义...&q；错误？

For循环中的变量行为不符合预期.[C17]

在C中访问数组中的特定值

Printf()在C中打印终止字符之后的字符，我该如何解决这个问题？

C：如何将此代码转换为与数组一起使用？

我正在try 将QSORT算法实现为C++中的泛型函数

带有数组指针的 struct 在print_stack()函数中打印随机数

计算SIZE_MAX元素的长数组的大小

为什么孤儿进程在 Linux 中没有被 PID 1 采用，就像我读过的一本书中声称的那样？

为什么这里的符号没有解析？