Interview Question on link list 

Write a recessive function to reverse a singly linked list in c? some time interviewer at beginning level can ask this type of question to test the basic concept of data structure in c. This is one of famous interview question on data structure.

How to 

The general recursive algorithm for this is:

  1. Divide

    the list in


    parts – first node and rest of the list.

  2. Recursively call reverse for the


    of the linked list.

  3. Link





  4. Fix



      Below is pictorial action of above steps to reverse a singly linked list by recursion.

Reverse a Linked List using Recursion in C

void rev_rec(struct node** head_ref)
    struct node* first;
    struct node* rest;
    /* empty list */
    if (*head_ref == NULL)
    /* suppose first = {1, 2, 3}, rest = {2, 3} */
    first = *head_ref; 
    rest  = first->next;
    /* List has only one node */
    if (rest == NULL)
 /* reverse the rest list and put the first element at the end */
    first->next->next  = first; 
    /* tricky step -- see the diagram */
    first->next  = NULL;         
    /* fix the head pointer */
    *head_ref = rest;             


Related Contents to follow