Recursion On Linked List

Recursive Operations On Linked List:

• Insertion in linked list using recursion
• Deletion linked list using recursion
• Copy linked list using recursion
• Count nodes in linked list using recursion

See Also:

C Program To Merge Two Arrays
C Program For Array Representation Of Sparse Matrix
C Program To Perform Insertion, Deletion, Searching & Traversal In Singly Linked List
C Program To Perform Insertion, Deletion, Sorting In Doubly Linked List - (Simple)
C Program To Sort A Doubly Linked List (Descending Order)

C Program To Merge Two Linked Lists

C Program To Reverse Linked List
C Program To Implement Circular Singly Linked List
C Program To Implement Circular Doubly Linked List
C Program For Polynomial Multiplication Using Linked List 
C Program For Polynomial Addition Using Linked List
C Program For Linked List Representation Of Sparse Matrix
C Program To Concatenate Two Linked Lists
C Program To Perform Recursion On Linked List

Insertion, Deletion, Traversal, Reversal And Search Operation on Arrays
Doubly Linked List - Insertion, Traversal, Searching, Delete Node, Delete List

Example Program To Perform Recursive Operations On Linked List(in C):

---

  #include<stdio.h>
  #include<stdlib.h>

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

  struct node *head1, *head2, *head3;
  int nCount = 0;

  /*
   * creates node and fill the given data
   */
  struct node * createNode(int data) {
        struct node *ptr = (struct node *) malloc(sizeof (struct node));
        ptr->data = data;
        ptr->next = NULL;
        return ptr;
  }

  /* insertion operation - using recursion */
  void insert(struct node ** myNode, int data) {
        if (*myNode) {
                insert(&(*myNode)->next, data);
        } else {
                *myNode = createNode(data);
        }
        return;
  }

  /* copy contents from list1 to list 2 - using recursion*/
  void copyList(struct node *list1, struct node **list2) {
        if (list1) {
                *list2 = createNode(list1->data);
                copyList(list1->next, &(*list2)->next);
        }
        return;
  }

  /* compare contenst of list 1 & list 2 - using recursion */
  int compareList(struct node *list1, struct node *list2) {
        if (!list1 && !list2) {
                printf("Both First & Second List are same!!\n");
                return (1);
        }

        if (!list1 || !list2 || (list1->data != list2->data)) {
                printf("Both Lists are not equal!!\n");
                return 0;
        } else {
                return (compareList(list1->next, list2->next));
        }

  }

  /* delete the given list using recursion */
  struct node * deleteList(struct node *ptr) {
        struct node *temp;
        if (ptr){
                temp = ptr->next;
                free(ptr);
                deleteList(temp);
        }
        return NULL;
  }

  /* no of nodes in the given list */
  int nodeCount(struct node *ptr) {
        if (ptr) {
                nCount++;
                nodeCount(ptr->next);
        }
        return;
  }

  /* travese the whole list and print the contents of each node */

  int walkList(struct node *ptr) {

        int i = 0;

        while (ptr) {

                printf("%d ", ptr->data);

                ptr = ptr->next;

                i++;

        }

        return (i);

  }

  int main (int argc, char *argv[]) {

        int data, i, n;

        FILE *fp1;

        fp1 = fopen(argv[1], "r");

        if (!fp1) {

                printf("Unable to open file\n");

                exit(0);

        }

        /* read data from the input file */

        while (fscanf(fp1, "%d", &data) != EOF) {

                insert(&head1, data);

        }

        printf("\nData in First Linked List:\n");

        n = walkList(head1);

        printf("\nNo of elements in linked list: %d\n", n);

        printf("\nCopied data from linked list 1 to 2!!");

        copyList(head1, &head2);

        printf("\n\nData in Second Linked List:\n");

        n = walkList(head2);

        nodeCount(head2);

        printf("\nNo of elements in linked list: %d\n\n", nCount);

        compareList(head1, head2);

        printf("\n");

        head1 = deleteList(head1);

        head2 = deleteList(head2);

        return 0;

  }

  Output: (Recursion in Singly Linked List - Example Program in C)

  jp@jp-VirtualBox:~/$ cat input1.txt 
  1 3 5 7 9 11 13 15
  jp@jp-VirtualBox:~/$ ./a.out input1.txt 

  Data in First Linked List:
  1 3 5 7 9 11 13 15 
  No of elements in linked list: 8
  
  Copied data from linked list 1 to 2!!

  Data in Second Linked List:
  1 3 5 7 9 11 13 15 
  No of elements in linked list: 8

  Both First & Second List are same!!