Sort List (M)
題目
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
題意
將鏈表排序，要求不能使用額外空間，且時間復雜度為\(O(NlogN)\)，
思路
鏈表不好操作快排和堆排，使用歸并排序(分治法)：每次利用快慢指標找到鏈表的中間位置，將其斷開為左右兩個子鏈表，待這兩個子鏈表排序后，利用歸并將它們再重新合并為一個有序鏈表，遞回處理，
代碼實作
Java
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null;
return merge(sortList(head), sortList(mid));
}
private ListNode merge(ListNode head1, ListNode head2) {
ListNode head = new ListNode(0);
ListNode cur = head;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
cur.next = head1;
head1 = head1.next;
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
cur.next = head1 == null ? head2 : head1;
return head.next;
}
}
JavaScript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var sortList = function (head) {
if (!head || !head.next) {
return head
}
let slow = head, fast = head
while (fast.next && fast.next.next) {
fast = fast.next.next
slow = slow.next
}
let left = head, right = slow.next
slow.next = null
left = sortList(left)
right = sortList(right)
let dummy = new ListNode()
let p = dummy
while (left && right) {
let node = left.val <= right.val ? left : right
let tmp = node.next
node.next = null
p.next = node
p = p.next
node === left ? (left = tmp) : (right = tmp)
}
p.next = !left ? right : left
return dummy.next
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/174036.html
標籤：其他