题目：Sort a linked list in O(n log n) time using constant space complexity.
思路：要求时间复杂度O(nlogn)
知识点：归并排序，链表找到中点的方法
存在的缺点：边界条件多考虑！！！
/** * LeetCode Sort List Sort a linked list in O(n log n) time using constant space complexity. * 题目：将一个单链表进行排序，，时间复杂度要求为o(nlogn) * 思路：1时间复杂度为o(nlog n)的排序算法有：归并排序、快排（期望）、堆排序 * 2、单链表排序用归并排序，双链表排序用快排 * Definition for singly-linked list. * class ListNode { *int val; *ListNode next; *ListNode(int x) { *val = x; *next = null; *} * } */package javaTrain;class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public class Train4 { public ListNode sortList(ListNode head) {if(head == null || head.next == null)return head;ListNode fast = head;ListNode slow = head;while(fast.next.next != null && slow.next != null){fast = fast.next.next;//使得当遍历完该链表之后一个指向中间一个指向末尾，即找到链表中点slow = slow.next;}ListNode list2 = slow.next;slow.next = null;head = sortList(head);list2 = sortList(list2);return merge(head,list2);}private static ListNode merge(ListNode list1,ListNode list2){if(list1 == null) return list2;if(list2 == null) return list1;ListNode head = new ListNode(0);ListNode last = head; while(list1.next != null && list2.next != null){if(list1.val <= list2.val){last.next = list1;list1 = list1.next;}else{last.next = list2;list2 = list2.next;}last = last.next;}if(list1 != null)last.next = list1;else if(list2 != null)last.next = list2;return head.next;}}
偶尔为街头独特的风景驻足，
