Sort List 체인 테이블 정렬 @LeetCode

요구 시간은 O(nlogn)입니다. 가장 적합한 것은mergesort입니다. 매번 n/2에서 끊고 두 단락을sort로 귀속시킨 다음merge를 시작합니다.
공간은 O(logn)입니다. 스택 공간을 사용했습니다.

package Level4;

import Utility.ListNode;

/**
 * Sort List
 * 
 * Sort a linked list in O(n log n) time using constant space complexity.
 *
 */
public class S144 {

	public static void main(String[] args) {
		int[] list = {1,4,2,3};
		ListNode head = ListNode.create(list);
		ListNode h = sortList(head);
		h.print();
	}

	public static ListNode sortList(ListNode head) {
		if(head==null || head.next==null){	//  
			return head;
		}
		ListNode fast = head;
		ListNode slow = head;
		ListNode preSlow = head;
		//  
		while(fast!=null && fast.next!=null){
			fast = fast.next.next;
			preSlow = slow;
			slow = slow.next;
		}
		
//		System.out.println(preSlow.val);
		//  ， 
		preSlow.next = null;
		
		ListNode first = sortList(head);		//  
		ListNode second = sortList(slow);	//  
		ListNode dummy = new ListNode(-1);
		ListNode dummyCur = dummy;
		while(first!=null && second!=null){	//  
			if(first.val<second.val){
				dummyCur.next = first;
				first = first.next;
			}else if(second.val<=first.val){
				dummyCur.next = second;
				second = second.next;
			}
			dummyCur = dummyCur.next;
		}
		
		while(first != null){
			dummyCur.next = first;
			first = first.next;
			dummyCur = dummyCur.next;
		}
		
		while(second != null){
			dummyCur.next = second;
			second = second.next;
			dummyCur = dummyCur.next;
		}
		
		return dummy.next;
    }
}

Merge Sort:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public static ListNode sortList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode slow = head, fast = head, preSlow = head;
		while (fast != null && fast.next != null) {
			preSlow = slow;
			slow = slow.next;
			fast = fast.next.next;
		}
		preSlow.next = null;
		ListNode h1 = sortList(head);
		ListNode h2 = sortList(slow);
		return mergeList(h1, h2);
	}

	public static ListNode mergeList(ListNode h1, ListNode h2) {
		ListNode dummyHead = new ListNode(0);
		ListNode dummy = dummyHead;
		while (h1 != null && h2 != null) {
			if (h1.val <= h2.val) {
				dummy.next = h1;
				h1 = h1.next;
			} else {
				dummy.next = h2;
				h2 = h2.next;
			}
			dummy = dummy.next;
		}

		while (h1 != null) {
			dummy.next = h1;
			h1 = h1.next;
			dummy = dummy.next;
		}
		while (h2 != null) {
			dummy.next = h2;
			h2 = h2.next;
			dummy = dummy.next;
		}
		return dummyHead.next;
	}
}