reverse a linked list using recursion error

Question

I am understanding recursion and so I tried writing reverse a linked list program. I have written the below function but it says segmentation error (core dumped).

void reverse(){
    if (head -> next == NULL){
        return;
    }
    reverse (head -> next);
    struct node *q = (struct node*) malloc (sizeof(struct node));
    q = head -> next;
    q -> next = head;
    head -> next = NULL;
}

Please can someone guide me. Thank you.

Answer 1

Recursion is a way of thinking that's gained by practice. So congratulations on your attempt. It's not correct, but don't be discouraged.

Here are two ways to go about the problem.

Your goal is to subdivide it into a smaller version of itself plus a (hopefully easy and fast to compute) incremental step that takes a solution to the smaller version to a complete solution. This is the essence of recursive thinking.

First try: Think of the list as a head element plus the "rest of the list." I.e.,

L = empty or
  = h . R

where h is the head element R is the rest of the list, and dot . is joining a new element to the list. Reversing this list consists of reversing R, then appending h on the end:

rev(L) = empty if L is empty
       = rev(R) . h otherwise

This is a recursive solution because we can call the reverse function recursively to solve the slightly smaller problem of reversing R, then add a little work to append h, and that gives us the complete solution.

The problem with this formulation is that appending h is more expensive than you'd like. Since we have a singly linked list with only a head pointer, it's time consuming: traverse the whole list. But it will work fine. In C it would be:

NODE *rev(NODE *head) {
  return head ? append(head, rev(head->next)) : NULL;
}

NODE *append(NODE *node, NODE *lst) {
  node->next = NULL;
  if (lst) {
    NODE *p;
    for (p = lst; p->next; p = p->next) /* skip */ ;
    p->next = node;
    return lst;
  }
  return node;
}

So how to get rid of the bad performance? It's frequently the case that different recursive formulations of a problem have different efficiencies. So some trial and error is often involved.

Next try: Think about the computation in terms of dividing the list into two sublists: L = H T, so rev(L) = rev(T) + rev(H). Here plus + is list concatenation. The key is that if I know rev(H) and want to add a new element at its head, the element to add is the first element in T. If this seems fuzzy, let H = [a, b, c] and T = [d, e]. Then if I already know rev(H) = [c, b, a] and want to prepend the next element at the head, I want d, which is the first element of T. In our little notation, you can write this observation just so:

rev(H + (d . T)) = rev(T) + ( d . rev(H) )

So this looks very good. In both cases (getting the head of T and moving it to the head of rev(H)), I'm only interested in the head of the list, which is very efficient to access.

Of course if T is empty, then rev(H) = rev(L). This is the answer!

Writing this as recursive procedure.

NODE *rev(NODE *t, NODE *rev_h) {
  if (t) {                // if t has some elements
    NODE *tail = t->next;   // save the tail of T
    t->next = rev_h;        // prepend the head to rev(H)
    return rev(tail, t);    // recur to solve the rest of the problem
  }
  return rev_h; // otherwise T is empty, so the answer is rev(H)
}

At the start, we don't know anything at all about rev(H), so T is the whole list:

NODE *reversed_list = rev(list, NULL);

The next thing to note is that this function is tail recursive: the recursive call is executed just before the function returns. This is good! It means we can easily rewrite it as a loop:

NODE *rev(NODE *t, NODE *rev_h) {
recur:
  if (t) {                // if t has some elements
    NODE *tail = t->next;   // save the tail of T
    t->next = rev_h;        // prepend the head to rev(H)
    rev_h = t;              // "simulate" the recursive call
    t = tail;               //   by setting both args
    goto recur;             //   and going back to the start
  }
  return rev_h; // otherwise T is empty, so the answer is rev(H)
}

You can always do this transformation with tail-recursive calls. You should think hard about why this works.

Now the goto is easily rewritten as a while loop, and we can make rev_h a local variable initialized to NULL, since that's all the initial call does:

NODE *rev(NODE *t) {
  NODE *rev_h = NULL;
  while (t) {             // while t has some elements
    NODE *tail = t->next;   // save the tail of T
    t->next = rev_h;        // prepend the head to rev(H)
    rev_h = t;              // "simulate" the recursive call
    t = tail;               //   by setting both args
  }
  return rev_h; // otherwise T is empty, so the answer is rev(H)
}

An in-place linked list reverser that needs only a small constant amount of space!

And look! We never had to draw funny box and arrow diagrams or think about pointers. It "just happened" by careful reasoning about how to subdivide the problem into smaller instances of itself, the essence of recursion. It's also a nice way to see that loops are just a special kind of recursion. Cool, no?

Answer 2

Shouldn't reverse take an argument? And please be aware that you cannot change a pointer in a function and have that be a lasting change. That is, in a C function, the only lasting changes are those that use *var = something.

Answer 3

I am assuming that you have something like the followings predefined in your .c file

typedef struct node node_t;
struct node {
    int some_data;
    node_t *next;
};

/* Your linked list here */
typedef struct {
    node_t *head;
    node_t *foot; /* to keep track of the last element */
} list_t;

In your function, there are a few mistakes you made

• not providing any input arguments
• access head->next when the program has no idea where to find head

Hence, resulting in the most frustrating error in C -- segmentation fault!

Instead, you should try the following:

void reverse(list_t *mylinkedlist){
    if (mylinkedlist->head->next == NULL) {
        return;
    }
    /* do something */
}