196-对链表进行归并排序

秒速五厘米 2022-10-30 09:29 198阅读 0赞

**题目如下：**  
对链表进行归并排序，且时间复杂度符合O(nlogn).

**解题思路如下：**  
1、定义len=1;遍历链表，计算出链表的总长度为len；  
2、申请一个结点dummy，作为链表的头结点  
3、进入for (int i = 1; i < len; i \*= 2)循环，然后调用cut切割函数，cut切割值以指数形式增长，每次乘以二，之后每一次调用cut，通过两两合并的方式将链表归并。然后调用 merge(left, right); //对合并后的局部链表进行内部排序

**代码及注释如下;**

ListNode *cut(ListNode *head, int k)//按要求切割链表
    {
        
    	ListNode *p = head;
    	while (--k && p != nullptr)
    	{
        
    		p = p->next;
    	}
    	if (p == nullptr)
    	{
        
    		return nullptr;
    	}
    	head = p->next;
    	p->next = nullptr; //断开链表，合成局部链表 
    	return head;
    }
    
    ListNode *merge(ListNode *p, ListNode *q)//归并两个有序链表
    {
        
    	ListNode *node = new ListNode(0);//申请一个新结点 
    	ListNode *s = node;
    	while (p != nullptr && q != nullptr)//进行归并 
    	{
        
    		if (p->val > q->val)
    		{
        
    			s->next = q;
    			s = s->next;
    			q = q->next;
    		}
    		else
    		{
        
    			s->next = p;
    			s = s->next;
    			p = p->next;
    		}
    	}
    	s->next = (p != nullptr) ? p : q;
    	return node->next;
    }
    
    ListNode *sortList(ListNode *head)//归并排序方法
    {
        
    	if (head == nullptr || head->next == nullptr)
    	{
        
    		return head;
    	}
    	int len = 1;
    	ListNode *p = head;
    	while (p->next != nullptr)//计算传入链表的总长度 
    	{
        
    		len++;
    		p = p->next;
    	}
    	
    	ListNode *dummy = new ListNode(0);//申请一个结点，作为链表的头结点 
    	dummy->next = head;//链接 
    	
    	for (int i = 1; i < len; i *= 2)
    	{
        
    		//cur表示等待分割的链表的第一个结点，p用来表示已经合并好的最后一个结点 
    		ListNode *cur = dummy->next;
    		ListNode *p = dummy;
    		while (cur != nullptr)
    		{
        
    			ListNode *left = cur;
    			ListNode *right = cut(left, i);//切割链表 
    			cur = cut(right, i); //cur走到切割后的局部链表的尾结点的下一个结点
    			p->next = merge(left, right); //对合并后的局部链表进行内部排序 
    			while (p->next != nullptr)
    			{
        
    				p = p->next; //p指向合并后的局部链表的尾结点
    			}
    		}
    	}
    	return dummy->next;//返回归并排序完成后总链表的头结点 
    }

**代码演示图如下:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/ee476464f61c43ac93d7bcd685133f68.png