Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3 Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0 Output: -1->0->3->4->5

難度：medium

題目：排列鏈表，時(shí)間復(fù)雜度為O(n logn) 空間復(fù)雜度為O(1).

思路：快速排序

Runtime: 232 ms, faster than 9.03% of Java online submissions for Sort List.
Memory Usage: 41.8 MB, less than 100.00% of Java online submissions for Sort List.

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/ public class Solution {public ListNode sortList(ListNode head) {quickSort(head, null);return head;}private void quickSort(ListNode head, ListNode tail) {if (head == tail) {return;}int val = head.val;ListNode prevSwapPtr = head;for (ListNode ptr = head.next; ptr != tail; ptr = ptr.next) {if (ptr.val < val) {int t = prevSwapPtr.next.val;prevSwapPtr.next.val = ptr.val;ptr.val = t;prevSwapPtr = prevSwapPtr.next;}}head.val = prevSwapPtr.val;prevSwapPtr.val = val;quickSort(head, prevSwapPtr);quickSort(prevSwapPtr.next, tail);} }

總結(jié)

以上是生活随笔為你收集整理的148. Sort List的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。