c - 在不使用指向指针的指针的情况下反转链表

Question

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

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。其余的似乎都有效。

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

编辑:结构是:

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

Answer 1

您可以通过交换第一个和最后一个节点(浅拷贝)来反转列表，然后反转列表。这样最后一个节点的内容将在头指针已经指向的初始节点中结束。

这是一个实现:

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;
}

Demo.