这些小活动你都参加了吗?快来围观一下吧!>>
电子产品世界 » 论坛首页 » 嵌入式开发 » STM32 » sort-list

共1条 1/1 1 跳转至

sort-list

高工
2018-02-01 13:27:43     打赏

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

题意实现一个链表排序的算法;


方法一:刚开始想的是自己定义个比较函数,然后调用sort()函数进行实现

[cpp] view plain copy
  1. class Solution  

  2. {  

  3. public:  

  4.   

  5.     static bool cmp(ListNode* a, ListNode* b)  

  6.     {  

  7.         return a->val < b->val;  

  8.     }  

  9.   

  10.     ListNode* sortList(ListNode* head)  

  11.     {  

  12.         if (head==NULL)  

  13.         {  

  14.             return head;  

  15.         }  

  16.   

  17.         vector<ListNode*> arrList;  

  18.         ListNode* p = head;  

  19.   

  20.         while (p)  

  21.         {  

  22.             arrList.push_back(p);  

  23.             p = p->next;  

  24.         }  

  25.   

  26.         sort(arrList.begin(), arrList.end());  

  27.   

  28.         p = head = arrList[0];  

  29.   

  30.         for (int i=1; i<arrList.size(); i++)  

  31.         {  

  32.             p->next = arrList[i];  

  33.             p = p->next;  

  34.         }  

  35.   

  36.         arrList[arrList.size() - 1]->next = NULL;  

  37.   

  38.         return head;  

  39.   

  40.     }  

  41. };  


方法二:因为题目要求的时间负责度O(nlogn), 故可以考虑归并排序的思想;

归并排序的一把步骤:

(1)将待排序数组去中间点并一分为二;

(2)递归地对左半部分进行归并排序;

(3)递归地对右半部分进行归并排序;

(4)将两个半部分进行合并,得到结果;

所以对应此题,可以分为三个小问题;

(1)找到链表中点;

(2)写出merge函数,即如何合并链表

(3)写出mergesort函数,实现上述步骤;

[cpp] view plain copy
  1. class Solution  

  2. {  

  3. public:  

  4.   

  5.     //找到链表中间位置  

  6.     ListNode* findMid(ListNode* head)  

  7.     {  

  8.         ListNode* slow = head;  

  9.         ListNode* fast = head;  

  10.   

  11.         while (fast!=NULL && fast->next!=NULL && fast->next->next!=NULL)  

  12.         {  

  13.             slow = slow->next;  

  14.             fast = fast->next->next;  

  15.         }  

  16.   

  17.         return slow;  

  18.     }  

  19.   

  20.     //合并两个有序链表  

  21.     ListNode* mergeList(ListNode* h1, ListNode* h2)  

  22.     {  

  23.         if (h1 == NULL)  

  24.         {  

  25.             return h2;  

  26.         }  

  27.         else if (h2 == NULL)  

  28.         {  

  29.             return h1;  

  30.         }  

  31.         else  

  32.         {  

  33.             ListNode* head = NULL;  

  34.             if (h1->val>h2->val)  

  35.             {  

  36.                 head = h2;  

  37.                 h2 = h2->next;  

  38.             }  

  39.             else  

  40.             {  

  41.                 head = h1;  

  42.                 h1 = h1->next;  

  43.             }  

  44.   

  45.             ListNode* p = head;  

  46.             while (h1 && h2)  

  47.             {  

  48.                 if (h1->val < h2->val)  

  49.                 {  

  50.                     p->next = h1;  

  51.                     h1 = h1->next;  

  52.                 }  

  53.                 else  

  54.                 {  

  55.                     p->next = h2;  

  56.                     h2 = h2->next;  

  57.                 }  

  58.                 p = p->next;  

  59.             }  

  60.   

  61.             if (h1) p->next = h1;  

  62.             if (h2) p->next = h2;  

  63.   

  64.             return head;  

  65.         }  

  66.     }  

  67.     ListNode* sortList(ListNode* head)  

  68.     {  

  69.         if (head == NULL || head->next == NULL)  

  70.         {  

  71.             return head;  

  72.         }  

  73.   

  74.         ListNode* mid = findMid(head);  

  75.   

  76.         ListNode* h2 = sortList(mid->next);  

  77.         mid->next = NULL;  

  78.         ListNode* h1 = sortList(head);  

  79.   

  80.         return mergeList(h1, h2);  

  81.     }  

  82. }; 




共1条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]