Problem with splitting LinkedList and Merge Sorted lists

[Z feng]

I know there were many different solutions online, but I really want to know is there a way to make my function work.

I am making a program to split a linked list to half, and print out its middle element in the list.

LinkedList* returnMiddleList(LinkedList* head)
{
  LinkedList *head1 = head;
  LinkedList *head2 = head;

  int i = 0;
  int j = 0;

  while ((head2->next) && (head2->next->next))
  {
    if ((i % 2 == 1)&& (head2->next->next))
    {
      head1 = head1->next;
      j++;
    }

    head2 = head2->next;
    i++;
  }
  cout << endl;
  cout << "Number " << j << " is the middle number of the list, and it's " << head1->num << endl;
  cout << endl;


  head2 = head1->next;//assign the begin of second half

  head1->next = NULL;
  
//THIS PART IS BAD BUT IT WORKED...I can't assign head1->next = NULL;, it //will skip over the first element in the second half list. 

  LinkedList* nullNode = new LinkedList;
  nullNode->next = NULL;
  head1->next = nullNode;//first half to stop
  


  return head2;
}

void printList(LinkedList* head)
{
  const LinkedList *p;
  int i = 0;

  for (p = head; p; p = p->next, i++)
  {
    if(p->next)
    {
      if (i < 10)
        cout << "0" << i << ":";
      else
        cout << i << ":";
      cout << p->num << "  " << endl;
  //    cout << "Memeory Address : " << list << endl;
    }
    else
      break;
  }
}

Problem came in when I tried to merge the sorted split lists by using this function:

LinkedList* mergeSortedLists(LinkedList* head1, LinkedList* head2)
{
  if (head1 == NULL) 
    return head2;
  else if (head2 == NULL) 
    return head1;
  else if (head1->num <= head2->num)
  {
    head1->next = mergeSortedLists(head1->next, head2);
    return head1;
  }
  else
  {
    head2->next = mergeSortedLists(head1, head2->next);
    return head2;
  }
}

Because the merge function had to be recursive, it didn't assign a tail for the end of the list. Since at the end of the

returnMiddleList

I have to assign the extra node to end the first half list, it had an extra element. So during the merging, it will merge that extra nullNode, too. (for example: when we print the merged list which have 10 elements, we will have 11 elements instead of 0-9, and 11th value just had random number.

So I am thinking whether I should change my return mid value function, or I should change the mergeSortedLists to solve the problem? =/

Here is the whole thing if you want to have a look about what is all going on. :)

#include <cstdlib>
#include <iostream>
#include <ctime>
using namespace std;


struct LinkedList
{
  int num;
  LinkedList *next;
};

void populateList(LinkedList* );
void printList(LinkedList*);
LinkedList* returnMiddleList(LinkedList* );
void sum(LinkedList*);
LinkedList* splitList(LinkedList*);
LinkedList* MergeSort(LinkedList*);
LinkedList* mergeSortedLists(LinkedList*, LinkedList*);


int main()
{
  LinkedList *head = new LinkedList;
  populateList(head);
  cout << ">>>-- printList --<<<" << endl;
  printList(head);
  cout << endl;
  cout << endl;


 
  cout << ">>>-- returnMiddleList --<<<" << endl;
  LinkedList *head2 = returnMiddleList(head);

  cout << "--- First Half ---" << endl;
  printList(head);
  sum(head);
  cout << endl;
  cout << "*** MergeSort ***" << endl;
  LinkedList *sortedList = MergeSort(head);
  printList(sortedList);

  cout << endl;
  cout << endl;

  cout << "--- Second Half ---" << endl;
  printList(head2);
  sum(head2);
  cout << endl;
  cout << "*** MergeSort ***" << endl;
  LinkedList *sortedList2 = MergeSort(head2);
  printList(sortedList2);

  cout << endl;
  cout << endl;

  cout << ">>>-- mergeLists --<<<" << endl;
  LinkedList *result = mergeSortedLists(sortedList, sortedList2);
  printList(result);

  cout << endl;
}

void populateList(LinkedList* head)
{
  LinkedList *temp;
//  srand ( time(NULL) );
  for (int i = 0; i < 10; i++)
  { 

    head->num = rand() % 100;
    temp = new LinkedList;

    head->next = temp;
    head = head->next;
  }
  head->next = 0;
}

void printList(LinkedList* head)
{
  const LinkedList *p;
  int i = 0;

  for (p = head; p; p = p->next, i++)
  {
    if(p->next)
    {
      if (i < 10)
        cout << "0" << i << ":";
      else
        cout << i << ":";
      cout << p->num << "  " << endl;
  //    cout << "Memeory Address : " << list << endl;
    }
    else
      break;
  }
}


LinkedList* returnMiddleList(LinkedList* head)
{
  LinkedList *head1 = head;
  LinkedList *head2 = head;

  int i = 0;
  int j = 0;

  while ((head2->next) && (head2->next->next))
  {
    if ((i % 2 == 1)&& (head2->next->next))
    {
      head1 = head1->next;
      j++;
    }

    head2 = head2->next;
    i++;
  }
  cout << endl;
  cout << "Number " << j << " is the middle number of the list, and it's " << head1->num << endl;
  cout << endl;


  head2 = head1->next;//assign the begin of second half

  head1->next = NULL;

  LinkedList* nullNode = new LinkedList;
  nullNode->next = NULL;
  head1->next = nullNode;//first half to stop

  return head2;
}


void sum(LinkedList* head)
{
  int sum = 0;
  for (LinkedList *p = head; p->next; p = p->next)
    sum = sum + p->num;
  cout << "Sum = " << sum << endl;
}

LinkedList* splitList(LinkedList* head)
{
  LinkedList* half;

  if ((head == NULL) || (head->next == NULL))
    return NULL;
  else 
  {
    half = head->next;
    head->next = half->next;
    half->next = splitList(half->next);
    return half;
  }
}

LinkedList* MergeSort(LinkedList* head)
{
  LinkedList *secondList;

  if (head == NULL)
    return NULL;
  else if (head->next == NULL)
    return head;
  else
  {
    secondList = splitList(head);
    return mergeSortedLists(MergeSort(head), MergeSort(secondList));
  }
}

LinkedList* mergeSortedLists(LinkedList* head1, LinkedList* head2)
{
  LinkedList* tail = 0; // for temporary 
  if (head1 == NULL) 
    return head2;
  else if (head2 == NULL) 
    return head1;
  else if (head1->num <= head2->num)
  {
    head1->next = mergeSortedLists(head1->next, head2);
    return head1;
  }
  else
  {
    head2->next = mergeSortedLists(head1, head2->next);
    return head2;
  }
}

I don't know whether I clear the problem or not...if not, please ask. I am really bad at explaining...sorry... :(