博文中会简要介绍Leetcode P0148题目分析及解题思路。
“Sort List”是一道比较经典的利用归并排序的题目。这道题要求时间复杂度是O(nlogn)。
其实看到O(nlogn)这样的时间复杂度，除了归并排序（Merge Sort）以外，还能想到快排序（Quick Sort）。但是后者是平均时间复杂度为O(nlogn)，最坏时间复杂度是O(n^2)，考虑到这题中是链表排序，无法随机选择pivot，如果每次都选择最左边的作为pivot，但是不巧地遇到一个降序序列，那么快排序就会退化为插入排序，变成O(n^2)的时间复杂度。所以这道题优先考虑使用归并排序。
Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
以下是Java的题解代码实现。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null)
return head;
return this.mergeSort(head);
}
private ListNode mergeSort(ListNode head) {
if (head.next == null)
return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Split the linked list into two parts
ListNode half = slow.next;
slow.next = null;
ListNode l1 = this.mergeSort(head);
ListNode l2 = this.mergeSort(half);
return this.merge(l1, l2);
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode l3 = new ListNode(0), tail = l3;
while (l1 != null && l2 != null) {
tail.next = (l1.val <= l2.val)? l1: l2;
tail = tail.next;
l1 = (tail == l1)? l1.next: l1;
l2 = (tail == l2)? l2.next: l2;
}
if (l1 != null)
tail.next = l1;
if (l2 != null)
tail.next = l2;
return l3.next;
}
}
以下是C++的题解代码实现。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head)
return head;
return this->_MergeSort(head);
}
private:
ListNode* _MergeSort(ListNode *head) {
if (!head->next)
return head;
ListNode *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *half = slow->next;
slow->next = nullptr;
ListNode *l1 = this->_MergeSort(head);
ListNode *l2 = this->_MergeSort(half);
return this->_Merge(l1, l2);
}
ListNode *_Merge(ListNode *l1, ListNode *l2) {
ListNode *l3 = new ListNode(0), *tail = l3;
while (l1 && l2) {
tail->next = (l1->val <= l2->val)? l1: l2;
tail = tail->next;
l1 = (tail == l1)? l1->next: l1;
l2 = (tail == l2)? l2->next: l2;
}
if (l1)
tail->next = l1;
if (l2)
tail->next = l2;
return l3->next;
}
};