在不使用指针指针的情况下反转链接列表

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

演示.