Reverse a linked list without using a pointer to pointer

Question

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

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.

How can I modify begin_list without a double pointer?

Edit: Structure is :

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

Answer 1

There are three main ways in which a function can provide a computed value to its caller.

1. It can return that value, or an object containing it, or a pointer to such an object (provided, in the last case, that the pointed-to object outlives the function call).

2. It can modify an object visible to the caller via a pointer provided by the caller.

3. It can record the computed value in a file-scope variable visible to the caller.

There are other alternatives, mostly involving I/O, but those are generally in the spirit of (3).

You are not permitted to use (1). You cannot use (2) in the way you propose. It may be that (3) is the expected answer, but that's ugly, and really should not be recommended. So what to do?

Maybe you just bite the bullet and use a file-scope variable, but if you're permitted to enlist the aid of the caller and / or place a requirement on the form of the list then you have another possibility: have the caller pass a pointer that does not change when the list is reversed -- i.e. a pointer to a structure that contains a pointer to the list head. The function does not then need to modify that pointer; it returns the new list head via the pointed-to object.

Oftentimes one does that sort of thing with a separate structure type representing the whole list. If you think for a moment, however, you will realize that your existing list node type already has suitable form. If you are unable to introduce a new structure, then, you can use your existing one -- just treat the first node in the list as a non-data-bearing handle on the rest of the elements. This is sometimes called a dummy head node, and lists that use one afford simpler function implementations in many respects.

Answer 2

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.

Here is an implementation:

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.

Answer 3

Have a look at this:

void reverse(struct node* head) {
    struct node *curr=head; 
    struct node *next=NULL;
    struct node *prev=NULL; 
    while(curr) { 
        next=curr->next; //we're basically stashing the next element
        curr->next=prev; //setting next pointer to the previous element
        prev=curr; //previous is now current
        curr=next; //and updating the current from the stashed value
    }
}