Practice problems for linked list and recursion

Introduction

Assume the node of the linked list has the following structure:


struct Node {
    int val;
    Node* next;
    Node(int value){
        val = value;
        next = NULL;
    }
};

Below are some recursive functions, try to explain their functionality:

Problem 1


void fun1(Node *head){
    if(head==NULL) return;
    cout<val<<" ";
    fun1(head->next);
}

Answer: The above function will print the given linked list.

Explanation:
When the head of a linked list is passed to the given function as an argument, it will print the value in the head node and call the same function for the next node. This will continue till we reach NULL.

So this will print the whole linked list from beginning to end.

Problem 2


void fun2(Node *head){
    if(head==NULL) return;
    fun2(head->next);
    cout<val<<" ";
}

Answer: It will print the linked list in reverse order.

Explanation:
When the head of a linked list is passed to the given function as an argument, it will call the same function for the next node and after doing so it will print the value in the head node. This will continue till we reach NULL.

So this will print the whole linked list after the current node before printing the current node. Hence the list will be printed in reverse order.

Problem 3


void fun3(Node* head){
    if(head == NULL) return;
    if(head->next==NULL){
        head->val += 1;
        return;
    }
    fun3(head->next);
}

Answer: Adds one to the last node of the linked list.

Explanation:
This function checks if the current node is the last node and if it is then adds 1 to it otherwise call the same function recursively for the next node.

Problem 4


int fun4(Node* head){
    if(head==NULL) return 0;
    return 1 + fun4(head->next);
}c

Answer: Returns the length of the linked list.

Explanation:
It adds 1 for each node that is not null and returns 0 for the empty linked list. In the end, we would have the sum of all 1's contributed by non-empty nodes and hence the length of the linked list.

Problem 5


bool fun5(Node* head, int x){
    if(head == NULL) return false;
    if(head->val == x) return true;
    return fun5(head->next, x);
}

Answer: Checks if there is a node with the value x in the given linked list.

Explanation:
The given function recursively iterates through the linked list and matches the values of nodes with x and returns true if they are equal else when the traversal ends returns false.

Problem 6


Node* fun6(Node* head, int x){
    if(head==NULL) return head;
    if(head->val == x) return head->next;

    head->next = fun6(head->next, x);
    return head;
}

Answer: Deletes the first occurrence of a node with the value x in the linked list.

Explanation:
The given function iterates recursively through the linked list and matches the value in the nodes with x. If they match, then it returns the whole linked list following the first matching node. In every function call, the next of the current node is updated. And in case of a match, the next pointer of the node just before the first matching node will be updated with the remaining linked list. Hence the first matching node will be removed.

Problem 7


Node* fun7(Node* head, int x){
    if(head==NULL) return head;
    if(head->val == x) return fun7(head->next, x);
    head->next = fun7(head->next, x);
    return head;
}

Answer: Deletes all the occurrences of nodes with the value x in the linked list.

Explanation: Similar to the previous question in this problem, the first node matching x is deleted but along with that, the function is recursively called for the next node as well. This would again remove the first node matching the value x in the remaining linked list. And hence all the occurrences of x will be removed from the linked list.

In this article, we went through a few example problems where we saw how recursive functions can be used to operate on linked lists. Problems like these are good for understanding how recursive functions can work on a linked list. I would highly recommend you to practice problems on Linked List.

Previous post Difference and similarities between HashSet, LinkedHashSet, and TreeSet in Java
Next post How to write C functions that modify the head pointer of a Linked List?

Leave a Reply

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