[LeetCode] 148. Sort List java

/**148. Sort List * @param head * @return O(nlogn)给链表排序 */ public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode slow = head; ListNode fast = head; ListNode pre = head; while (fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; } pre.next = null; head = sortList(head); slow = sortList(slow); return mergeTwoLists(slow, head); }

//能够有O(n lgn)时间复杂度的算法为，快速排序，堆排序，归并排序 //根据复杂度想到应该用merge sort方法 //beats 85.60%

利用slow和fast指针找到中点，之后将头和中间节点进行排序，将排序好的链表合并