反向链接列表，而无需使用指向指针的指针 [英] Reverse a linked list without using a pointer to pointer

问题描述

我已经使用以下代码成功实现了2个指针解决方案:

I have successfully implemented the 2 pointers solution using this code:

void list_reverse(t_list **begin_list)
{
    t_list *new_root;
    t_list *root;
    t_list *next;

    new_root = 0;
    root = *(begin_list);
    while (root)
    {
        next = root->next;
        root->next = new_root;
        new_root = root;
        root = next;
    }
    *begin_list = new_root;
}

哪个工作正常-至少根据我的测试.现在，我想尝试仅使用单个指针而不使用return来反向链接列表，因此我尝试将代码转换为void list_reverse(t_list *begin_list)，但是当然*begin_list = new_root不起作用，因为我不能更改begin_list.其余的似乎都可以.

Which works fine - at least according to my tests. Now I want to try to reverse a linked list using only a single pointer, without return, so I tried to convert my code to void list_reverse(t_list *begin_list), but of course the *begin_list = new_root doesn't work, because I can't change begin_list. The rest seems to work though.

如何在没有双指针的情况下修改begin_list?

How can I modify begin_list without a double pointer?

结构为:

typedef struct  s_list
{
    struct s_list   *next;
    void            *data;
}               t_list;

推荐答案

您可以通过交换第一个节点和最后一个节点(浅副本)，然后反转列表来反转列表.这样，最后一个节点的 content 最终将到达头指针已经指向的初始节点.

You can reverse the list by swapping the first and the last node in place (shallow copy), then reversing the list. This way the content of the last node would end up in the initial node, to which the head pointer is already pointing.

这是一个实现:

void swap(struct node *a, struct node *b) {
    struct node tmp = *a;
    *a = *b;
    *b = tmp;
}

void reverse(struct node *h) {
    // Null list and single-element list do not need reversal
    if (!h || !h->next) {
        return;
    }
    // Find the last node of the list
    struct node *tail = h->next;
    while (tail->next) {
        tail = tail->next;
    }
    // Swap the tail and the head **data** with shallow copy
    swap(h, tail);
    // This is similar to your code except for the stopping condition
    struct node *p = NULL;
    struct node *c = tail;
    do {
        struct node *n = c->next;
        c->next = p;
        p = c;
        c = n;
    } while (c->next != tail);
    // h has the content of tail, and c is the second node
    // from the end. Complete reversal by setting h->next.
    h->next = c;
}

演示.

这篇关于反向链接列表，而无需使用指向指针的指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！