本文共 2093 字，大约阅读时间需要 6 分钟。

1. 题目

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:输入: 4->2->1->3输出: 1->2->3->4示例 2:输入: -1->5->3->4->0输出: -1->0->3->4->5

来源：力扣（LeetCode）

2. 解题

2.1 归并排序

参考

class Solution {
   public:    ListNode* sortList(ListNode* head) {
           if(head == NULL || head->next == NULL)        	return head;        ListNode *fast = head->next, *slow = head, *rightHead;        //fast初始化先走一步，偶数个链表时，防止一边0个，一边2个节点        while(fast && fast->next)        {
           	fast = fast->next->next;        	slow = slow->next;        }        rightHead = slow->next;        slow->next = NULL;//先断开，再操作左右！！！        ListNode *right = sortList(rightHead);        ListNode *left = sortList(head);        return merge(left, right);    }    ListNode* merge(ListNode *left, ListNode *right)     {
       	ListNode *emptyHead = new ListNode(0);//虚拟哨兵头    	ListNode *cur = emptyHead;    	while(left && right)    	{
       		if(left->val < right->val)    		{
       			cur->next = left;    			left = left->next;    		}    		else    		{
       			cur->next = right;    			right = right->next;    		}    		cur = cur->next;    	}    	cur->next = (left == NULL ? right : left);    	cur = emptyHead->next;    	delete emptyHead;    	return cur;    }};

2.2 快速排序

class Solution {
   public:    ListNode* sortList(ListNode *head) {
           quicksort(head, NULL);        return head;    }    void quicksort(ListNode *head, ListNode *tail)     {
       	if(head == tail || head->next == NULL)        	return;        ListNode *mid = partition(head,tail);    	quicksort(head, mid);    	quicksort(mid->next, tail);    }    ListNode* partition(ListNode *head, ListNode *tail)    {
           int pivot = head->val;        ListNode *left = head, *cur = head->next;        while(cur != NULL && cur != tail)        {
               if(cur->val < pivot)            {
                   left = left->next;                swap(cur->val, left->val);            }            cur = cur->next;        }        swap(left->val, head->val);        return left;    }};

转载地址：https://michael.blog.csdn.net/article/details/101313065 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！