148. Sort List

public class Solution {
    private ListNode findMidNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    private ListNode merge(ListNode head1, ListNode head2){
        ListNode dummy = new ListNode(0);
        ListNode index = dummy;
        while(head1 != null && head2 != null)
        {
            if(head1.val < head2.val)
              {
                  index.next = head1;
                  head1 = head1.next;
              }
             else
              {
                  index.next = head2;
                  head2 = head2.next;
              }
              index = index.next;
        }
        if(head1 != null)  index.next = head1;
        else               index.next = head2;
        return dummy.next;
    }
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode mid = findMidNode(head);
        ListNode left = sortList(mid.next);
        mid.next = null;
        ListNode right = sortList(head);
        return merge(left,right);
    }
}