Add a number to alternate nodes of the Linked List

Write a recursive function that add 5 to the alternate nodes of the linked list. For example, if the list is

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

then the function should change the list to the below one

1 -> 7 -> 3 -> 9 -> 5 -> 11 -> 7 -> 13 -> 9 -> 15

Iterative Solution:

The code to add 5 to alternate nodes is straight forward.

We will just skip the alternate nodes. Below is the iterative solution for the same:

void addToAlternate(Node* h)
{
   while(h != NULL)
   {
      h = h->next;
      // Now we are at the node where we need to add 5
      if(h != NULL)
      {
         h->data += 5;
         h = h->next;
      }
   }
}

Recursive Solution:

In recursion we can use a flag that indicate if we need to skip the current node or add 5 to it

//If node need to be skipped then skipNode=1, else 0
void addToAlternate(Node* h, int skipNode = 1)
{
   if(h == NULL)
      return;
   if(skipNode)
   {
      // Do Nothing. Just call the recursive function
      addToAlternate(h->next,0);
   }
   else
   {
      // Add 5 to the current node
      h->data += 5;
      addToAlternate(h->next, 1);
   }
}

The above code can be more clearly written as below

//If node need to be skipped then skipNode=1, else 0
void addToAlternate(Node* h, int skipNode = 1)
{
   if(h == NULL)
      return;
   if(!skipNode)
   {
      // Add 5 to the current node
      h->data += 5;
   }
   addToAlternate(h->next, !skipNode);
}

Another way can be to look at pair of the node,

• skip the first Node,
• Add 5 to the second Node
• Call the function recursively for the third Node

 

void addToAlternate(Node* h)
{
   if(h == NULL || h->next == NULL)
      return;
   // Skip the first node
   h = h->next;
   // Add 5 to the second node
   h->data += 5;
   // Call recursively for the 3rd Node
   addToAlternate(h->next);
}