Split a LinkList based on alternate element?

Question

Say you are given a linklist as {a, b, a, b, a} , you need to divides up its nodes to make two smaller lists. The sublists should be made from alternating elements in the original list. So in this case one sublist should be {a, a, a} and the other should be {b, b}.

Answer 1

Try something like this

/* 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. */
void MoveNode(struct node** destRef, struct node** sourceRef) 
{
  /* the front source node  */
  struct node* newNode = *sourceRef; 

  /* Advance the source pointer */
  *sourceRef = newNode->next;

  /* Link the old dest off the new node */
  newNode->next = *destRef; 

  /* Move dest to point to the new node */
  *destRef = newNode; 
}

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(&a, &current); /* Move a node to list 'a' */
    if (current != NULL) 
    {
       MoveNode(&b, &current); /* Move a node to list 'b' */
    }
  }
  *aRef = a;
  *bRef = b;
}