Sort List (Java)

LeetCode

Sort a linked list in O(n log n) time using constant space complexity. There are two solutions of sort list question on Leetcode. I think the first one should be n(logn) time complexity, for the second one, I am not sure. looking forward to any comments

	public class SortList1{
	public ListNode sortList(ListNode head){
	if (head==null || head.next==null){
	return head;
	}
	ListNode counter=head;
	int len=0;
	while(counter!=null){
	counter=counter.next;
	len++;
	}
	ListNode[] headArray={head};
	return mergeSort(headArray, len);
	}
	private ListNode mergeSort(ListNode[] headArray, int len){
	if (len==1){
	ListNode temp=headArray[0];
	headArray[0]=headArray[0].next;
	temp.next=null;
	return temp;
	}
	ListNode left=mergeSort(headArray, len/2);
	ListNode right=mergeSort(headArray, len-len/2);
	return merge(left, right);
	}
	private ListNode merge(ListNode left, ListNode right){
	if (left==null)
	return right;
	if (right==null)
	return left;
	ListNode preHead=new ListNode (-1);
	ListNode end=preHead;
	while(left!=null && right !=null){
	if (left.val<right.val){
	end.next=left;
	left=left.next;
	}
	else{
	end.next=right;
	right=right.next;
	}
	end=end.next;
	}
	if (left!=null){
	end.next=left;
	}
	if (right!=null){
	end.next=right;
	}
	return preHead.next;
	}
	}

view raw SortListNew.java hosted with ❤ by GitHub

	Sort a linked list in O(n log n) time using constant space complexity.
	/**
	* Definition for singly-linked list.
	* class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	public ListNode sortList(ListNode head) {
	if (head==null||head.next==null){
	return head;
	}
	ListNode fast=head;
	ListNode slow=head;
	while(fast.next!=null && fast.next.next!=null){
	fast=fast.next.next;
	slow=slow.next;
	}
	ListNode right=slow.next;
	slow.next=null;
	ListNode left=head;
	left =sortList(left);
	right=sortList(right);
	return merge(left, right);
	}
	private ListNode merge(ListNode left, ListNode right){
	if (left==null){
	return right;
	}
	if (right==null){
	return left;
	}
	ListNode preHead=new ListNode(-1);
	ListNode end=preHead;
	while (left!=null && right!=null){
	if (left.val<right.val){
	end.next=left;
	left=left.next;
	}
	else{
	end.next=right;
	right=right.next;
	}
	end=end.next;
	}
	if (left!=null){
	end.next=left;
	}
	if (right!=null){
	end.next=right;
	}
	return preHead.next;
	}
	}

view raw Sort List.java hosted with ❤ by GitHub