Number of inversions in an Array.
June 13, 2012
Changing pointer passed to a function as argument
June 14, 2012

Recursive function to traverse linked list in reverse order

Write a recursive function to print the Linked list in reverse order …
Assume the below definition of Node of a Linked List

struct Node{
    int data;
    struct Node * link;
};

The function should accept pointer to the first Node of the list and should have the below signature:

/* Print the linked list in backward order (reverse) */
void printBack(struct Node* head);

Solution:

    void printBack (struct Node* head)
    {
        //terminating condition
        if(head == NULL)
            return;
        // Print the list and then print the Node
        printBack (head->next);
        printf("%d ", head->data);
    }

This is an example of Head Recursion. In Head recursion the recursive function is called first and then perform the operation.

Tail recursion is the case when we perform the operation first and then call the recursive function. For example, if we want to print the list in forward order, then we can use tail recursion as below:

    void printForward(struct Node* head)
    {
        //terminating condition
        if(head == NULL)
            return;
        printf("%d ", head->data);
        printForward (head->next);
    }

Leave a Reply

Your email address will not be published. Required fields are marked *