链表中进行排序的归并算法

清疚 2022-11-22 10:16 120阅读 0赞

链表排序的核心就是断链+合并链表

主要涉及到的操作是统计链表长度(来判断最大的合并步长) 分割链表 将两个链表进行合并

  1. /*struct ListNode {
  2. int val;
  3. ListNode *next;
  4. ListNode() : val(0), next(nullptr) {}
  5. ListNode(int x) : val(x), next(nullptr) {}
  6. ListNode(int x, ListNode *next) : val(x), next(next) {}
  7. };*/
  8. ListNode* sortList(ListNode* head) {
  9. /* 此为归并算法进行求解
  10. if(!head) return nullptr; //此判断仅用来排除[]测试点
  11. //尝试采用递归的归并排序进行解题
  12. //使用快慢指针找到中间结点
  13. ListNode *p,*q;
  14. p=head;
  15. q=head->next;
  16. if(!q) return p; //只有一个结点
  17. while(q && q->next){
  18. p=p->next;
  19. q=q->next->next;
  20. }
  21. //将链表断开
  22. q=p->next;
  23. p->next=nullptr;
  24. head=sortList(head);
  25. q=sortList(q);
  26. return Merge(head,q);
  27. */
  28. //使用迭代归并进行排序
  29. ListNode *_head=new ListNode;
  30. _head->next=head;
  31. int count=count_len(head);
  32. ListNode *cur,*pre;
  33. for(int i=1;i<count;i*=2){
  34. pre=_head; cur=_head->next; //进行初始化
  35. while(cur!=nullptr){
  36. ListNode *h1=cur;
  37. ListNode *h2=cut_list(h1,i);
  38. cur=cut_list(h2,i);
  39. h1=Merge(h1,h2);
  40. pre->next=h1;
  41. while(pre->next){
  42. pre=pre->next;
  43. }
  44. }
  45. //print(_head->next);
  46. }
  47. return _head->next;
  48. }
  49. //测试打印输出
  50. /*void print(ListNode *head){
  51. while(head){
  52. cout<<head->val<<" ";
  53. head=head->next;
  54. }
  55. cout<<endl;
  56. }*/
  57. //分割链表
  58. ListNode* cut_list(ListNode *head,int step){
  59. if(!head) return nullptr;
  60. ListNode *p,*q;
  61. p=head;
  62. for(int i=1;i<step && p->next!=nullptr;i++){ //此处应该当心最后剩下的链表不足分割 使用p->next判断的优点是即使不足分割 其代码形式和能够完整分割相同
  63. p=p->next;
  64. }
  65. q=p->next;
  66. p->next=nullptr;
  67. return q;
  68. }
  69. //获取链表的长度
  70. int count_len(ListNode *head){
  71. int count=0;
  72. while(head){
  73. head=head->next;
  74. count++;
  75. }
  76. return count;
  77. }
  78. //将两个链表进行归并
  79. ListNode* Merge(ListNode *head,ListNode *q){
  80. ListNode *_head=new ListNode;
  81. ListNode *p1,*p2,*tem;
  82. p1=head; p2=q; tem=_head;
  83. while(p1 && p2){
  84. if(p1->val <= p2->val){
  85. tem->next=p1;
  86. p1=p1->next;
  87. }
  88. else{
  89. tem->next=p2;
  90. p2=p2->next;
  91. }
  92. tem=tem->next;
  93. }
  94. if(p1) tem->next=p1;
  95. else tem->next=p2;
  96. return _head->next;
  97. }
  98. }

发表评论

表情:
评论列表 (有 0 条评论,120人围观)

还没有评论,来说两句吧...

相关阅读

    相关 排序--归并排序

    要求在空间复杂度为O(1)的情况下对链表进行排序,在不考虑时间复杂度的情况下可以考虑冒泡排序,只对链表中的值进行操作,这样时间复杂度为O(n^2)。用归并排序,时间复杂度为O(

    相关 排序-归并

    链表排序,可以插入排序,我就不写了。 实现归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Con