Oct 252016
 

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

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)