链表的归并排序

两种方法
递归法(自顶向下法)
迭代法(自底向上法)
递归法（自顶向下法）

这里链表与数组不同的是链表无法随机访问，在数组中我们都能精准的找到中心位置，这里我们接纳快慢指针来确定中心节点，然后通过递归到单个元素然后分割链表，再链接链表（下面将一一讲解）
快慢指针确定中心节点

1. /*head为已知条件*/
2. Listnode* tail=nullptr;
3. Listnode* slow=head;
4. Listnode* fast=head;
5. while(fast!=tail)         //快指针多移动一次到尾时，慢指针则为中间节点
6. {
7.    slow=slow->next;
8.    fast=fast->next;
9.    if(fast!=tail)
10.    {
11.       fast=fast->next;
12.    }
13.    Listnode* mid=slow;    //中间节点
14. }

复制代码

分割链表

1. ListNode* apart_list(ListNode* head,ListNode* tail)
2. {
3.     if(head==nullptr) return nullptr;
4.     if(head->next==tail) return head;
5.     Listnode* slow=head;
6.     Listnode* fast=head;
7.     while(fast!=tail)         //快指针多移动一次到尾时，慢指针则为中间节点
8.     {
9.        slow=slow->next;
10.        fast=fast->next;
11.        if(fast!=tail)         //头闭尾开只有一个元素head 无法继续分割返回head节点
12.        {
13.           fast=fast->next;
14.        }
15.        Listnode* mid=slow;    //中间节点
16.     }
17.    
18.     /*这里的merge为合并函数*/
19.     /*我们这里递归分割左右链表，递归到只有一个元素无法分割后链接两边节点*/
20.     return merge(apart_list(head,mid),apart_list(mid,tail));
21. }
22. /*
23.     假如链表如下:
24.     1   4   3   5   2  
25. 第一次分割1,nullptr中间节点为3 也就是  return merge(apart_list(1,3),apart_list(3,nullptr))
26. 第二次分割1,3中间节点为2  然后 return  merge(apart_list(1,2),apart_list(2,3))   
27. 第三次分割1,2无法进行分割 此时满足head->next=tail 1节点下一节点置空 返回1节点
28. 第四次分割2,3同理 置空2节点的下一节点后返回2节点
29. 然后通过执行merge(2,3)将分割的单个节点2和3有序链接  返回给上一级递归
30. 同理3,nullptr也是如此
31. */

复制代码

链接链表

这个就简单了就是归并两个有序链表

1. ListNode* merge(ListNode* l,ListNode* r)
2. {
3.    ListNode* temp=new ListNode(0);
4.    ListNode* l_now=l;
5.    ListNode* r_now=r;
6.    ListNode* now=temp;
7.    
8.    /*都有元素则比较大小*/
9.    while(l_now!=nullptr&&r_now!=nullptr)
10.    {
11.       if(l_now->val<=r_now->val)
12.       {
13.           now->next=l_now;
14.           l_now=l_now->next;
15.       }  
16.       else
17.       {
18.           now->next=r_now;
19.           r_now=r_now->next;
20.       }
21.       now=now->next;
22.    }
23.    
24.    /*链接剩下的元素*/
25.    if(l_now!=nullptr)
26.    {
27.        now->next=l_now;
28.    }
29.    else now->next=r_now;
30.    return temp->next;
31. }

复制代码

完整代码

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode() : val(0), next(nullptr) {}
7. *     ListNode(int x) : val(x), next(nullptr) {}
8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9. * };
10. */
11. class Solution {
12. public:
13.     ListNode* apart_list(ListNode* head,ListNode* tail)
14.     {
15.         if(head==nullptr) return nullptr;
16.         if(head->next==tail)
17.         {
18.             head->next=nullptr;
19.             return head;
20.         }
21.         ListNode* slow=head,*fast=head;
22.         while(fast!=tail)
23.         {
24.             slow=slow->next;
25.             fast=fast->next;
26.             if(fast!=tail)
27.             {
28.                 fast=fast->next;
29.             }
30.         }
31.         ListNode* mid=slow;
32.         return merge(apart_list(head,mid),apart_list(mid,tail));
33.     }
34.     ListNode* merge(ListNode* l,ListNode* r)
35.     {
36.         ListNode* temp=new ListNode(0);
37.         ListNode* l_now=l;
38.         ListNode* r_now=r;
39.         ListNode* now=temp;
40.         while(l_now!=nullptr&&r_now!=nullptr)
41.         {
42.             if(l_now->val<=r_now->val)
43.             {
44.                 now->next=l_now;
45.                 l_now=l_now->next;
46.             }
47.             else
48.             {
49.                 now->next=r_now;
50.                 r_now=r_now->next;
51.             }
52.             now=now->next;
53.         }
54.         if(l_now!=nullptr)
55.         {
56.            now->next=l_now;
57.         }
58.         else if(r_now!=nullptr)
59.         {
60.            now->next=r_now;
61.         }
62.         return temp->next;
63.     }
64.     ListNode* sortList(ListNode* head) {
65.         return apart_list(head,nullptr);
66.     }
67. };

复制代码

时间复杂度为O(nlogn)空间复杂度为O(logn)


自底向上法

和数组一样我们需要不断的增加分区间的间隔

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     ListNode *next;
6. *     ListNode() : val(0), next(nullptr) {}
7. *     ListNode(int x) : val(x), next(nullptr) {}
8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9. * };
10. */
11. class Solution {
12. public:
13.     ListNode* sortList(ListNode* head) {
14.         if(head==nullptr)
15.         {
16.             return head;
17.         }
18.         int length=0;
19.         ListNode* node=head;
20.         while(node!=nullptr)
21.         {
22.             length++;
23.             node=node->next;
24.         }
25.         ListNode* temp=new ListNode(0,head);
26.         for(int len=1;len<length;len*=2)     //增加半区间
27.         {
28.             ListNode* pre=temp,*now=temp->next;
29.             while(now!=nullptr)
30.             {
31.                 ListNode* head1=now;
32.                 for(int i=1;i<len&&now->next!=nullptr;i++)
33.                 {
34.                     now=now->next;
35.                 }
36.                 ListNode*head2=now->next;
37.                 now->next=nullptr;            //分割
38.                 now=head2;
39.                 for(int i=1;i<len&&now!=nullptr&&now->next!=nullptr;i++)
40.                 {
41.                     now=now->next;
42.                 }
43.                 ListNode* next=nullptr;
44.                 if(now!=nullptr)
45.                 {
46.                     next=now->next;
47.                     now->next=nullptr;
48.                 }
49.                 ListNode* marged=merge(head1,head2);
50.                 pre->next=marged;
51.                 while(pre->next!=nullptr)
52.                 {
53.                     pre=pre->next;
54.                 }
55.                 now=next;
56.             }
57.         }
58.         return temp->next;
59.     }
60.     ListNode* merge(ListNode* l,ListNode* r)
61.     {
62.         ListNode* temp=new ListNode(0);
63.         ListNode* l_now=l;
64.         ListNode* r_now=r;
65.         ListNode* now=temp;
66.         while(l_now!=nullptr&&r_now!=nullptr)
67.         {
68.             if(l_now->val<=r_now->val)
69.             {
70.                 now->next=l_now;
71.                 l_now=l_now->next;
72.             }
73.             else
74.             {
75.                 now->next=r_now;
76.                 r_now=r_now->next;
77.             }
78.             now=now->next;
79.         }
80.         if(l_now!=nullptr)
81.         {
82.            now->next=l_now;
83.         }
84.         else if(r_now!=nullptr)
85.         {
86.            now->next=r_now;
87.         }
88.         return temp->next;
89.     }
90. };

复制代码

时间复杂度为O(logn)空间复杂度为O(n)

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。