Practice problems for linked list and recursion

Last Updated on March 12, 2022 by Ria Pathak

Introduction

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

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

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

class Node:
	def __init__(self, val):
		self.val = val
		self.next = None

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

Problem 1

void fun1(Node *head){
    if(head==NULL) return;
    printf("%d ",head->val);
    fun1(head->next);
}

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

def func1(head):
	if head is None:
		return head
	print(head.val, end=" ")
	func1(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.

void fun2(struct Node *head){
    if(head==NULL) return;
    fun2(head->next);
    printf("%d ",head->val);
}

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

def func2(head):
	if head is None:
		return head
	func2(head.next)
	print(head.val, end=" ")

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(struct Node* head){
    if(head == NULL) return;
    if(head->next==NULL){
        head->val += 1;
        return;
    }
    fun3(head->next);
}

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

def func3(head):
	if head is None:
		return head
	if head.next is None:
		head.val += 1
		return
	func3(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(struct Node* head){
    if(head==NULL) return 0;
    return 1 + fun4(head->next);
}

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

def func4(head):
	if head is None:
		return 0
	return 1 + func4(head.next)

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);
}

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

def func5(head, x):
	if head is None:
		return False
	if head.val == x:
		return True
	return func5(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

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

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;
}

def func6(head, x):
	if head is None:
		return head
	if head.val == x:
		return head.next
	head.next = func6(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

struct Node* fun7(struct 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;
}

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;
}

def func7(head, x):
	if head is None:
		return head
	if head.val == x:
		return func7(head.next, x)
	head.next = func7(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.