Sort List

Java

//solution 1: merge sort
class Solution {
		public ListNode sortList(ListNode head) {
			if (head == null || head.next == null) {
				return head;
			}
			//find mid
			ListNode mid = findMid(head);
			ListNode right = sortList(mid.next);
			mid.next = null; //中间要断开 -- 需要先右后左边
			ListNode left = sortList(head);
			
			return merge(left, right);
		}
		
		private ListNode findMid(ListNode head) {
			ListNode slow = head, fast = head.next;
			while (fast != null && fast.next != null) {
				fast = fast.next.next;
				slow = slow.next;
			}
			return slow; //双数时候是之前以为，单数为中间一位
		}
		
		private ListNode merge(ListNode head1, ListNode head2) {
			ListNode dummy = new ListNode(-1);
			ListNode cur = dummy;
			while (head1 != null && head2 != null) {
				if (head1.val < head2.val) {
					cur.next = head1;
					head1 = head1.next;
				} else {
					cur.next = head2;
					head2 = head2.next;
				}
				cur = cur.next;
			}
			if (head1 != null) cur.next = head1;
			if (head2 != null) cur.next = head2;
			return dummy.next;
		}
}

Time Complexity : O(nlogn); //????
Space Complexity : O(1); //并没有额外空间