split.cpp

/*
CSCI 104: Homework 1 Problem 1

Write a recursive function to split a sorted singly-linked
list into two sorted linked lists, where one has the even 
numbers and the other contains the odd numbers. Students 
will receive no credit for non-recursive solutions. 
To test your program write a separate .cpp file and #include
split.h.  **Do NOT add main() to this file**.  When you submit
the function below should be the only one in this file.
*/

#include "split.h"
#include <cstddef>

/* Add a prototype for a helper function here if you need */
void addNode(Node*& list, Node*& num);

void split(Node*& in, Node*& odds, Node*& evens)
{
  /* Add code here */
  // WRITE YOUR CODE HERE
  // mod to see if even/odd
  // add to correct list

  //in: 1, 2, 3
  if (in == NULL) {
    return;
  }

  Node* rest = in->next; //save the next for recursive call
  in->next = NULL; //remove

  if (in->value % 2 == 0) {
    addNode(evens, in);
  }
  else {
    addNode(odds, in);
  }

  split (rest, odds, evens);
  in = NULL; //don't save original
}

/* If you needed a helper function, write it here */
void addNode(Node*& list, Node*& num) {
  if (list == NULL) {
    //replace list with the num
    list = num;
    return;
  }
  //if not null, we haven't reached end of the list so keep moving until the end
  addNode(list->next, num);
}