单链表排序（快速排序、归并排序）

r囧r小猫 2022-08-26 04:51 272阅读 0赞

本题目来源于LeetCode,具体如下：

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

题目要求复杂度O(nlogn)，因此我们很自然考虑使用快速排序或者归并排序，但是后来经过实践证明，使用快速排序总是AC超时，归并排序则可以正确AC。

分析一下原因，个人认为是与测试数据有关，因为快速排序不能保证算法复杂度一定是O(nlogn)，当数据比较集中时，即使做随机选取key值，算法的复杂度也非常接近O(N^2)，因此会出现超时，所以考虑使用归并排序。

下面是采用归并排序的思路已经AC代码：

主要考察3个知识点，  
知识点1：归并排序的整体思想  
知识点2：找到一个链表的中间节点的方法  
知识点3：合并两个已排好序的链表为一个新的有序链表  
  
归并排序的基本思想是：找到链表的middle节点，然后递归对前半部分和后半部分分别进行归并排序，最后对两个以排好序的链表进行Merge。

#include <iostream>
    #include <string>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <fstream>
    using namespace std;
    
    struct ListNode {
    	int val;
    	ListNode *next;
    	ListNode(int x) : val(x), next(NULL) {}
    };
    
    class Solution {
    public:
    
    	ListNode* mergeLists(ListNode *a, ListNode *b) //合并两个已经排序的链表
    	{
    		if (a == NULL) return b ;
    		if (b == NULL) return a ;
    		ListNode *ret = NULL ;
    		ListNode *tail = NULL ;
    		
    		ret = new ListNode(-1) ;
    		tail = ret ;
    		while (a && b)
    			if (a->val < b->val)
    			{
    				tail->next = a ;
    				tail = tail->next ;
    				a = a->next ;
    			}
    			else
    			{
    				tail->next = b ;
    				tail = tail->next ;
    				b = b->next ;
    			}
    		if (a)
    			tail->next = a ;
    		if (b)
    			tail->next = b ;
    
    		ListNode *del = ret ;
    		ret = ret->next ;
    		delete del ;
    
    		return ret ;
    	}
    
    	ListNode *getMid(ListNode *head) //得到中间节点
    	{ 
    		if (!head) return NULL ;
    		if (!head->next) return head ;
    
    		ListNode *slow = head ;
    		ListNode *fast = head->next ;
    
    		while (fast && fast->next)
    		{
    			slow = slow->next ;
    			fast = fast->next->next ;
    		}
    		return slow ;
    	}
    
    	ListNode *sortList(ListNode *head) { //合并排序
    
    		if (!head) return NULL ;
    		if (!head->next) return head ;
    
    		ListNode *mid = getMid(head) ;
    		ListNode *nextPart = NULL ;
    		if (mid)
    		{
    			nextPart = mid->next ;
    			mid->next = NULL ;
    		}
    
    		return mergeLists(
    			 sortList(head) ,
    			 sortList(nextPart) 
    			) ;
    	}
    };
    
    void insertBack(ListNode** head, ListNode** tail,  ListNode* n) //从尾部插入
    {	
    	if (n)
    	{
    		if (*head == NULL)
    		{
    			*head = n ;
    			*tail = n ;
    		}
    		else
    		{
    			(*tail)->next = n ;
    			*tail = n ;
    		}
    	}
    }
    
    int main(int argc, char** argv)
    {
    
    	ifstream in("data.txt") ;
    	ListNode* head = NULL ;
    	ListNode* tail = NULL ;
    	int val ;
    
    	Solution s ;
    	while(in >> val)
    	{
    		ListNode*tmp = new ListNode(val) ;
    		insertBack(&head, &tail, tmp) ;
    	}
    	head = s.sortList(head) ;
    	while(head)
    	{
    		cout << head->val << " " ;
    		head = head->next ;
    	}
    	cout << endl ;
    	return 0 ;
    }

下面再说一下自己AC超时的代码吧，

这里我尝试了两种实现方案：

第一种是：

在找划分点的过程中，维护连个链表Left 和Right 所有不大于key的元素都链到Left上，大于key的链到Right上，最后再将Left, key , Right三部分连接起来。

代码如下：

#include <iostream>
    #include <string>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <fstream>
    using namespace std;
    
    struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
    };
    
    class Solution {
    public:
    	inline void insertBack(ListNode** head, ListNode** tail,  ListNode* n) //从尾部插入
    	{	
    		if (n)
    		{
    			if (*head == NULL)
    			{
    				*head = n ;
    				*tail = n ;
    			}
    			else
    			{
    				(*tail)->next = n ;
    				*tail = n ;
    			}
    		}
    	}
    
        ListNode *sortList(ListNode *head) {
    		if (!head) return NULL ;
    		if (head->next == NULL) return head ;
    		//划分
    		ListNode *tmpNode = head ;
    		head = head->next ;
    		ListNode *sleft = NULL , *eleft = NULL ;
    		ListNode *sright = NULL , *eright = NULL ;
    		while (head)
    		{
    			ListNode *insNode = head ;
    			head = head->next ;
    
    			insNode->next = NULL ;
    			if (insNode->val > tmpNode->val)
    				insertBack(&sright, &eright, insNode) ;
    			else
    				insertBack(&sleft, &eleft, insNode) ;
    		}
    
    		//递归调用	
    		sleft = sortList(sleft) ;
    		sright = sortList(sright) ;
    
    		//下面三句话第一次没有加上，调试了一下午才找到原因
    		eleft = sleft ;
    		if (eleft)
    		{
    			while(eleft->next)
    				eleft = eleft->next ;
    		}
    
    		//拼接起来
    		if (eleft)
    		{
    			head = sleft ;
    			eleft->next = tmpNode ;
    		}
    		else
    			head = tmpNode ;
    		tmpNode->next = sright ; //连接起来
    
    		//返回结果
    		return head ;
        }
    };
    
    int main(int argc, char** argv)
    {
    	ifstream in("data.txt") ;
    	ListNode* head = NULL ;
    	ListNode* tail = NULL ;
    	int val ;
    
    	Solution s ;
    	while(in >> val)
    	{
    		ListNode*tmp = new ListNode(val) ;
    		s.insertBack(&head, &tail, tmp) ;
    	}
    	head = s.sortList(head) ;
    	while(head)
    	{
    		cout << head->val << " " ;
    		head = head->next ;
    	}
    	cout << endl ;
    	return 0 ;
    }

第二种方案： 使用快排的另一种思路来解答。我们只需要两个指针 p 和 q ，这两个指针均往 next 方向移动，移动的过程中保持 p 之前的 key 都小于选定的 key ， p 和 q 之间的 key 都大于选定的 key ，那么当 q 走到末尾的时候便完成了一次划分点的寻找。如下图所示：

![SouthEast][]

实现代码如下：

#include <iostream>
    #include <string>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <fstream>
    using namespace std;
    
    struct ListNode {
    	int val;
    	ListNode *next;
    	ListNode(int x) : val(x), next(NULL) {}
    };
    
    class Solution {
    public:
    	ListNode* getPartation(ListNode *start, ListNode *end)
    	{
    		if (start == end) return start ;
    
    		ListNode *p1 = start ;
    		ListNode *p2 = p1->next ;
    		int key = start->val ;
    
    		while(p2 != end)
    		{
    			if (p2->val < key)
    			{
    				p1 = p1->next ;
    				swap(p1->val, p2->val) ; //找到一个比key小的数字，与p1到p2间的数交换，
    			}										//这之间的数都大于等于key
    			p2 = p2->next ;
    		}
    		swap(start->val, p1->val) ; //找到划分位置
    		return p1 ;
    	} ;
    
    	void QuickSort(ListNode* start, ListNode *end)
    	{
    		if (start != end)
    		{
    			ListNode *pt = getPartation(start, end) ;
    			QuickSort(start, pt) ;
    			QuickSort(pt->next, end) ;
    		}
    	}
    
    	ListNode *sortList(ListNode *head) {
    		QuickSort(head, NULL) ;
    		return head ;
    	}
    };
    
    void insertBack(ListNode** head, ListNode** tail,  ListNode* n) //从尾部插入
    {	
    	if (n)
    	{
    		if (*head == NULL)
    		{
    			*head = n ;
    			*tail = n ;
    		}
    		else
    		{
    			(*tail)->next = n ;
    			*tail = n ;
    		}
    	}
    }
    
    int main(int argc, char** argv)
    {
    
    	ifstream in("data.txt") ;
    	ListNode* head = NULL ;
    	ListNode* tail = NULL ;
    	int val ;
    
    	Solution s ;
    	while(in >> val)
    	{
    		ListNode*tmp = new ListNode(val) ;
    		insertBack(&head, &tail, tmp) ;
    	}
    	head = s.sortList(head) ;
    	while(head)
    	{
    		cout << head->val << " " ;
    		head = head->next ;
    	}
    	cout << endl ;
    	return 0 ;
    }

虽然使用快速排序的两种方案都因为超时不能AC，但是练习一下还是很有帮助的。

如果大家发现那里不对的地方还请批评指正，大家共同学习进步！先行谢过！

[SouthEast]: /images/20220824/a69888aeaa8a48b9b8ca47e8a97c19e6.png