本文主要是介绍140.Sort List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Sort a linked list in O(n log n) time using constant space complexity.
要求对一个链表排序时时间复杂度为o(nlgn)，空间复杂度为常数。时间复杂度为常数的排序算法有归并排序、快排、堆排序。比较之后选定归并排序。
/*** Sort a linked list in O(n log n) time using constant space complexity.* 要求对一个链表排序时时间复杂度为o(nlgn)，空间复杂度为常数。* 时间复杂度为常数的排序算法有归并排序、快排、堆排序。比较之后选定归并排序。* @date 20160526* @param head* @return*/public ListNode sortList(ListNode head) {/*如果链表为空或者只有一个节点，则直接返回head。*/if(head == null || head.next == null){return head;}else{/*采用归并排序的思想，采用快慢指针来对链表进行划分*/ListNode slow = head;ListNode fast = head.next;while(fast!=null && fast.next!=null){slow = slow.next;fast = fast.next.next;}ListNode mid = slow.next;slow.next = null;/*分别对前半部分和后半部分进行排序*/head = sortList(head);mid = sortList(mid);/*把两个有序的链表进行合并*/head = mergeTwoLists(head,mid);return head;}}/*** 对两个有序链表进行合并* @param l1* @param l2* @return*/public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1==null && l2==null){return null;}ListNode head = new ListNode(0);//先暂时保存一个临时的头结点ListNode p = head;while(l1!=null && l2!=null){if(l1.val <= l2.val){p.next = l1;l1=l1.next;p = p.next;}else{p.next = l2;l2=l2.next;p = p.next;}}if(l1 == null){p.next = l2;}else{p.next = l1;p = p.next;}return head.next;}这篇关于140.Sort List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
