title: Alternating split of a given Singly Linked List
body: <p>Write a function AlternatingSplit() that takes one list and divides up its nodes to make two smaller lists ‘a’ and ‘b’. The sublists should be made from alternating elements in the original list. So if the original list is 0->1->0->1->0->1 then one sublist should be 0->0->0 and the other should be 1->1->1.</p>
  
  <p>More details about the problem - <a href="http://www.geeksforgeeks.org/alternating-split-of-a-given-singly-linked-list/" rel="nofollow">http://www.geeksforgeeks.org/alternating-split-of-a-given-singly-linked-list/</a></p>
  
  <p>Now i made this code and it's running successfully</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  struct node
  {
      int num;
      node *next;
  };
  
  node *start1 = NULL, *start2 = NULL, *start3 = NULL;
  
  void push()
  {
      node *temp = (node *)malloc(sizeof(node));
      printf("Enter number = ");
      scanf("%d", &amp;temp-&gt;num);
      temp -&gt; next = start1;
      start1 = temp;
  }
  
  void split()
  {
      while(start1 != NULL)
      {
          node *temp1 = (node *)malloc(sizeof(node));
          temp1 -&gt;num = start1 -&gt;num;
          temp1-&gt;next = start2;
          start2 = temp1;
          start1 = start1 -&gt; next;
  
          if(start1 != NULL)
          {
              node *temp2 = (node *)malloc(sizeof(node));
              temp2 -&gt;num = start1 -&gt;num;
              temp2-&gt;next = start3;
              start3 = temp2;
              start1 = start1 -&gt; next;
          }
      }
  }
  
  int main()
  {
      int n;
      scanf("%d", &amp;n);
  
      while(n--)
          push();
  
      split();
  
      node *temp = start2;
  
      while(temp != NULL)
      {
          printf("%d  ", temp -&gt;num);
          temp = temp -&gt;next;
      }
  
      printf("\n");
      temp = start3;
  
      while(temp != NULL)
      {
          printf("%d  ", temp -&gt;num);
          temp = temp -&gt;next;
      }
  
      return 0;
  }
  </code></pre>
  
  <p>And the code provided with the question is - </p>
  
  <pre><code>/*Program to alternatively split a linked list into two halves */
  #include&lt;stdio.h&gt;
  #include&lt;stdlib.h&gt;
  #include&lt;assert.h&gt;
  
  /* Link list node */
  struct node
  {
      int data;
      struct node* next;
  };
  
  /* pull off the front node of the source and put it in dest */
  void MoveNode(struct node** destRef, struct node** sourceRef) ;
  
  /* Given the source list, split its nodes into two shorter lists.
  If we number the elements 0, 1, 2, ... then all the even elements
  should go in the first list, and all the odd elements in the second.
  The elements in the new lists may be in any order. */
  
  void AlternatingSplit(struct node* source, struct node** aRef, struct node** bRef) 
  {
      /* split the nodes of source to these 'a' and 'b' lists */
      struct node* a = NULL; 
      struct node* b = NULL;
  
      struct node* current = source;
  
      while (current != NULL) 
      {
          MoveNode(&amp;a, &amp;current); /* Move a node to list 'a' */
  
          if (current != NULL) 
          {
              MoveNode(&amp;b, &amp;current); /* Move a node to list 'b' */
          }
      }
  
      *aRef = a;
      *bRef = b;
  
  }
  
  /* Take the node from the front of the source, and move it to the front of the dest.
  It is an error to call this with the source list empty. 
  
  Before calling MoveNode():
  source == {1, 2, 3}   
  dest == {1, 2, 3}
  
  Affter calling MoveNode():
  source == {2, 3}      
  dest == {1, 1, 2, 3}      
  */
  
  void MoveNode(struct node** destRef, struct node** sourceRef) 
  {
      /* the front source node  */
      struct node* newNode = *sourceRef; 
      assert(newNode != NULL);
  
      /* Advance the source pointer */
      *sourceRef = newNode-&gt;next;
  
      /* Link the old dest off the new node */
      newNode-&gt;next = *destRef; 
  
      /* Move dest to point to the new node */
      *destRef = newNode; 
  }
  
  /* UTILITY FUNCTIONS */
  /* Function to insert a node at the beginging of the linked list */
  
  void push(struct node** head_ref, int new_data)
  {
      /* allocate node */
      struct node* new_node = (struct node*) malloc(sizeof(struct node));
  
      /* put in the data  */
      new_node-&gt;data  = new_data;
  
      /* link the old list off the new node */
      new_node-&gt;next = (*head_ref);     
  
      /* move the head to point to the new node */
      (*head_ref)    = new_node;
  }
  
  /* Function to print nodes in a given linked list */
  
  void printList(struct node *node)
  {
      while(node!=NULL)
      {
          printf("%d ", node-&gt;data);
          node = node-&gt;next;
      }
  } 
  
  /* Drier program to test above functions*/
  int main()
  {
      /* Start with the empty list */
      struct node* head = NULL;
      struct node* a = NULL;
      struct node* b = NULL;  
  
      /* Let us create a sorted linked list to test the functions
      Created linked list will be 0-&gt;1-&gt;2-&gt;3-&gt;4-&gt;5 */
      push(&amp;head, 5);
      push(&amp;head, 4);
      push(&amp;head, 3);
      push(&amp;head, 2);
      push(&amp;head, 1);                                    
      push(&amp;head, 0);  
  
      printf("\n Original linked List:  ");
      printList(head); 
  
      /* Remove duplicates from linked list */
      AlternatingSplit(head, &amp;a, &amp;b); 
  
      printf("\n Resultant Linked List 'a' ");
      printList(a);            
  
      printf("\n Resultant Linked List 'b' ");
      printList(b);            
  
      getchar();
  
      return 0;
  
  }
  </code></pre>
  
  <p>My query here is, which of these two codes are more efficient and more correct for this question, considering the time complexity, space complexity and every other factor?
  And why?
  A detailed explanation will be more helpful.</p>