Recursion: Print alternate node in a Linked List using recursion

Problem Statement:

You are given a LL, you need to print the alternate nodes using recursion

Example:

Input: 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

Output: 7 -> 5 -> 3 -> 1

Solution Explanation:

Take a variable flag, and alternatively change the value of flag from true to false and print the data when flag is true.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;


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


void solution(struct Node* node, bool flag=true)
{
    if (node == NULL)
       return;
    if (flag == true)
        cout << node->data << " "; 
    solution(node->next, !flag);
}

void insertNode(struct Node** head, int data)
{
   struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
   new_node->data = data;
   new_node->next = (*head);
   (*head) = new_node;
}
int main(){
   struct Node* head = NULL;
   insertNode(&head, 1);
   insertNode(&head, 2);
   insertNode(&head, 3);
   insertNode(&head, 4);
   insertNode(&head, 5);
   insertNode(&head, 6);
   insertNode(&head, 7);
   solution(head);
   return 0;
}

Output

7 5 3 1