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

    2

    parts – first node and rest of the list.

  2. Recursively call reverse for the

    rest

    of the linked list.

  3. Link

    rest

    to

    first

    .

  4. Fix

    head

    pointer

      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)
       return;  
 
    /* suppose first = {1, 2, 3}, rest = {2, 3} */
    first = *head_ref; 
    rest  = first->next;
 
    /* List has only one node */
    if (rest == NULL)
       return;  
 /* reverse the rest list and put the first element at the end */
    rev_rec(&rest);
    first->next->next  = first; 
    
    /* tricky step -- see the diagram */
    first->next  = NULL;         
 
    /* fix the head pointer */
    *head_ref = rest;             
}

Ref:

http://stackoverflow.com/questions/14080758/reversing-a-linkedlist-recursively-in-c                                                                           http://cslibrary.stanford.edu/105/LinkedListProblems.pdf



Related Contents to follow