gistfile1.java

public ListNode sortList(ListNode head) {

  ListNode node = head;
      int n =0;
      
      while(node!= null){
          n++;
          node = node.next;
      }
      node = head;
      return sortList(head, n);
  }

public ListNode sortList(ListNode head, int len){
    ListNode node = head;
    ListNode pre = null;
    ListNode left = head;
    ListNode right = null;
    
    if(len<2) return head;
    
    for(int i=1; i<=len/2; i++){
          pre = node;
          node = node.next;
    }
      
    pre.next = null;
    right = node;
    
    left = sortList(left, len/2);
    right = sortList(right, len-len/2);
    
    return mergeList(left, len/2,  right, len-len/2);
}

public ListNode mergeList(ListNode left, int leftLen, ListNode right, int rightLen){
	ListNode newListHead = null;
	ListNode node = null;
	ListNode leftNode = left, rightNode = right;
	   	
	if(left.val > right.val){
		newListHead = right;
		right = right.next;
		rightLen--;
		rightNode = right;
	}
	else{
		newListHead = left;
		left = left.next;
		leftLen--;
		leftNode = left;
	}
	
	node = newListHead;
		
	while(leftLen>0 || rightLen>0){
		
		if(leftLen>0 && rightLen>0){
			if(leftNode.val > rightNode.val){
				node.next = rightNode;
				rightNode = rightNode.next;
				rightLen--;
				node = node.next;
				node.next = null;
				
			}
			else{
				node.next = leftNode;
				leftNode = leftNode.next;
				leftLen--;
				node = node.next;
				node.next = null;
			}
		}
		else if(leftLen == 0){
			node.next = rightNode;
			break;
		}
		else if(rightLen == 0){
			node.next = leftNode;
			break;
		}
		
	}
	
	return newListHead;
}