Recursive Insertion and Traversal in Linked List Using C++

We are given with integer values that will be used to form a linked list. The task is to firstly insert and then traverse a singly linked list using a recursive approach.

Recursive addition of nodes at the end

• If head is NULL → add node to head

• Else add to head( head → next )

Recursive traversal of nodes

• If head is NULL → exit

• Else print( head → next )

Examples

Input − 1 - 2 - 7 - 9 - 10

Output − Linked list : 1 → 2 → 7 → 9 → 10 → NULL

Input − 12 - 21 - 17 - 94 - 18

Output − Linked list : 12 → 21 → 17 → 94 → 18 → NULL

Approach used in the below program is as follows

In this approach we will use functions to add nodes and traverse the singly linked list and call them recursively for next input.

• Take the structure SLLNode with integer and next pointer SLLNode* next.

• Function addtoEnd(SLLNode* head, int data) takes pointer to list’s head and integer for data part and adds node to the end of linked list.

• If the head pointer is NULL then the list is empty, now add a new node and set it as head. Add head → next as NULL. Return pointer to this node

• If head is not null the add node to head → next using head->next = addtoEnd(head- >next, data).

• Function traverseList(SLLNode* head) starts traversing from head and prints each value.

• If head is NULL then print NULL and return.

• Else print data value and traverse next using traverseList(head->next).

• Inside main create list using addtoEnd() and print the list using traverseList().

Example

#include <bits/stdc++.h>
using namespace std;
struct SLLNode {
   int data;
   SLLNode* next;
};
SLLNode* addtoEnd(SLLNode* head, int data){
   if (head == NULL){
      SLLNode *nodex = new SLLNode;
      nodex->data = data;
      nodex->next = NULL;
      return nodex;
   }
   else{
      head->next = addtoEnd(head->next, data);
    }
   return head;
}
void traverseList(SLLNode* head){
   if (head == NULL){
      cout <<"NULL";
      return;
   }
   cout << head->data << " -> ";
   traverseList(head->next);
}
int main(){
   SLLNode* head1 = NULL;
   head1 = addtoEnd(head1, 1);
   head1 = addtoEnd(head1, 8);
   head1 = addtoEnd(head1, 56);
   head1 = addtoEnd(head1, 12);
   head1 = addtoEnd(head1, 34);
   cout<<"Linked List is :"<<endl;
   traverseList(head1);
   return 0;
}

Output

If we run the above code it will generate the following Output

Linked List is :
1 -> 8 -> 56 -> 12 -> 34 -> NULL