title: Java LinkedList split in half (Merge sort)
body: <p>currently I am learning about merge sort with Linked List. I don't understand well how to  split the original ListNode in half.</p>
  <p>I cannot understand clearly why <code>ListNode left = mergeSort(head);</code> isn't head entire original ListNode not only left half? and why method getMiddleNode only return slowptr?</p>
  <p>as I assume, <code>ListNode left = mergeSort(head);</code> only contains left half but I want to understand how head is only become half.</p>
  <p>Thank you!</p>
  <p>Here is my code</p>
  <pre><code>class Solution {
    public ListNode mergeSort(ListNode head) {
      if(head == null || head.next == null){
        return head;
      }
      
      ListNode middle = getMiddleNode(head);
      
      ListNode left = mergeSort(head);
      ListNode right = mergeSort(middle);
      
      return merge(left, right);
    }
    
    ListNode getMiddleNode(ListNode head)
    {
      ListNode pre = null;
      ListNode slowptr = head;
      ListNode fastptr = head;
      
      while(fastptr != null || fastptr.next != null)
      {
        pre = slowptr;
        slowptr = slowptr.next;
        fastptr = fastptr.next.next;
      }
      
      pre.next = null;
      return slowptr;
    }
  }
  </code></pre>