1 题目
题目：链表排序（Sort List）
描述：在 O(nlogn) 时间复杂度和常数级的空间复杂度下给链表排序。
lintcode题号——98，难度——medium
样例1：
输入：list = 1->3->2->null
输出：1->2->3->null
解释：给链表排序.
样例2：
输入：list = 1->7->2->6->null
输出：1->2->6->7->null
解释：给链表排序.
2 解决方案
2.1 思路
??题目要求排序，在O(nlogn)时间复杂度内，空间复杂度要求常数级，满足时间复杂度的排序可以想到快速排序和归并排序，满足空间复杂度的只有快速排序，但题目排序的对象是链表，归并排序在数组上的空间复杂度是O(n)，但对链表排序时不需要额外的数据结构来存储临时数据，所以在链表上的归并排序的空间复杂度只有O(1)，本题使用快排和归并都可以。
2.2 时间复杂度
??时间复杂度为O(n * log n)。
2.4 空间复杂度
??空间复杂度为O(1)。
3 源码
细节：
- 使用快、慢指针的方式来找链表的中点。
- fast指针起点位置向后移动一位，符合整数计算偏左的特点，且不用特殊处理链表长度为2的情况。
- 递归时先处理后半段，再将中点赋空，断开后半段，再处理前半段。
C++版本：
/**
* Definition of singly-linked-list:
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
/**
* @param head: The head of linked list.
* @return: You should return the head of the sorted linked list, using constant space complexity.
*/
ListNode* sortList(ListNode *head) {
// write your code here
if (head == nullptr || head->next == nullptr) // 跳过链表长度为0和1的情况
{
return head;
}
// 找到链表中点
ListNode * mid = head;
ListNode * fast = head->next; // fast指针起点位置向后移动一位，符合整数计算偏左的特点，且不用特殊处理链表长度为2的情况
while (fast != nullptr && fast->next != nullptr)
{
mid = mid->next;
fast = fast->next->next;
}
ListNode * right = sortList(mid->next); // 先排后半段
mid->next = nullptr; // 断开后半段
ListNode * left = sortList(head); // 再排前半段
return mergeTwoSortedList(left, right);
}
ListNode * mergeTwoSortedList(ListNode * left, ListNode * right)
{
if (left == nullptr)
{
return right;
}
if (right == nullptr)
{
return left;
}
ListNode dummyNode(0);
ListNode * cur = &dummyNode;
while (left != nullptr && right != nullptr)
{
if (left->val < right->val)
{
cur->next = left;
left = left->next;
cur = cur->next;
}
else
{
cur->next = right;
right = right->next;
cur = cur->next;
}
}
if (left != nullptr)
{
cur->next = left;
}
if (right != nullptr)
{
cur->next = right;
}
return dummyNode.next;
}
