title: reverse half of the list
body: <p>I was asked to write a function reverseHalves() that rearranges a given linked list so that the first half of the nodes is moved to the back of the second half. e.g.  </p>
  
  <p>Given a linked list <code>[1 2 3 4 5 6]</code>, the resulting list should be <code>[4 5 6 1 2 3]</code>.<br>
  When given a linked list with an <em>odd number of nodes</em>,  the list should be split with the first half  having an additional node. That is, given the list <code>[1 2 3 4 5]</code>, the resulting list should be <code>[4 5 1 2 3]</code>. </p>
  
  <p>But the my function will give a infinite output...</p>
  
  <pre><code>typedef struct _listnode{
      int item;
      struct _listnode *next;
  } ListNode;
  
  typedef struct _linkedlist{
      int size;
      ListNode *head;
      ListNode *tail;
  } LinkedList;
  </code></pre>
  
  <p>Here are the functions I used:</p>
  
  <pre><code>// printList will print out the value in every nodes until there is a NULL
  void printList(LinkedList *ll);
  ListNode * findNode(LinkedList *ll, int index);
  int insertNode(LinkedList *ll, int index, int value);
  
  void reverseHalves(LinkedList *ll)
  {
      int index;
      ListNode *new_head, *new_tail;
      new_head = NULL;
      new_tail = NULL;
  
      // determine the index of new tail, and the new head which is index+1*
      index = (ll-&gt;size + 1) / 2;
  
      // get the new head by findNode func,whose index is index+1 
      // make new_head point to the node found*
      new_head = findNode(ll, index);
  
      // make initial tail-&gt;next be the initial head*
      ll-&gt;tail-&gt;next = ll-&gt;head;
  
      // set the head to be the new head
      ll-&gt;head = new_head;
  
      insertNode(ll, ll-&gt;size, -1);
      new_tail = findNode(ll, ll-&gt;size);
      new_tail = NULL;
  }
  </code></pre>