首页 > 代码库 > 算法题：合并两个有序的链表

算法题：合并两个有序的链表

2024-08-12 07:54:04   225人阅读

说明：本文仅供学习交流，转载请标明出处，欢迎转载！

             题目：已知有两个有序的单链表，其头指针分别为head1和head2，实现将这两个链表合并的函数：

          Node* ListMerge(Node *head1,Node *head2)

       这个算法很像我们排序算法中的归并排序，只能说“很像”，因为思想是一样的，但是这个与归并排序还是有区别的，区别如下：

       1.归并排序是针对有序数组，而这里是有序链表；

       2.归并排序排序的时间复杂度为o(nlogn)，而这里的时间复杂度最坏情况下为O(m+n)，最好的情况下为O(min{m,n})。

       3.归并排序需要重新申请空间，而这里无需再重新申请空间，只需改变链表结点的指针指向。

       而这里算法的思想跟归并排序是一样的，都是对两个待归并的线性表分别设置1个指针，比较这两个当前指针的大小，将小的结点加入到合并后的线性表中，并向后移动当前指针。若两个线性表中，至少有一个表扫描完，走将对应的另一个表之间整体添加到合并后的线性表中。在这里：链表和数组的区别在于，链表只需要改变当前合并序列尾指针的位置，而数组则要将剩下的值依次复制到归并表的尾部。

        算法的递归实现如下：

 

[cpp] view plain copy
 
  1. Node *ListMerge1(Node *head1,Node *head2)//采用递归的方法实现  
  2. {  
  3.     if(head1==NULL)  
  4.         return head2;  
  5.     if(head2==NULL)  
  6.         return head1;  
  7.     Node *head=NULL;  
  8.     if(head1->value < head2->value)  
  9.     {  
  10.         head=head1;  
  11.         head->next=ListMerge1(head1->next,head2);  
  12.     }  
  13.     else  
  14.     {  
  15.         head=head2;  
  16.         head->next=ListMerge1(head1,head2->next);  
  17.     }  
  18.     return head;  
  19. }  

 

         算法的非递归实现如下：

 

[cpp] view plain copy
 
  1. Node *ListMerge(Node *head1,Node *head2)  
  2. {  
  3.     if(!head1) return head2;  
  4.     if(!head2) return head1;  
  5.     Node *head=NULL;//合并后的头指针  
  6.     Node *p1=head1;//p1用于扫描链表1  
  7.     Node *p2=head2;//p2用于扫描链表2  
  8.     if(head1->value<head2->value)  
  9.     {  
  10.         head=head1;  
  11.         p1=head1->next;  
  12.     }  
  13.     else  
  14.     {  
  15.         head=head2;  
  16.         p2=head2->next;  
  17.     }  
  18.     Node *p=head;//p永远指向最新合并的结点  
  19.     while(p1 && p2)//如果循环停止，则p1或p2至少有一个为NULL  
  20.     {  
  21.         if(p1->value<p2->value)  
  22.         {  
  23.             p->next=p1;  
  24.             p1=p1->next;  
  25.         }  
  26.         else  
  27.         {  
  28.             p->next=p2;  
  29.             p2=p2->next;  
  30.         }  
  31.         p=p->next;  
  32.     }  
  33.     if(p1)//如果链1还没走完  
  34.     {  
  35.         p->next=p1;  
  36.     }  
  37.     else if(p2)//如果链2还没走完  
  38.     {  
  39.         p->next=p2;  
  40.     }  
  41.     return head;  
  42. }  

 

          整个测试代码如下：

 

[cpp] view plain copy
 
  1. #include<iostream>  
  2. using namespace std;  
  3. struct Node  
  4. {  
  5.     int value;  
  6.     Node* next;  
  7.     Node(int v):value(v){}  
  8. };  
  9. /*创建一个链表，1->2->3->4->5->6->7*/  
  10. Node* CreateList1()//创建一个有序的单链表1  
  11. {  
  12.    Node *head;  
  13.    Node *n1=new Node(1);  
  14.    Node *n3=new Node(3);  
  15.    Node *n5=new Node(5);  
  16.    Node *n7=new Node(7);  
  17.    Node *n9=new Node(9);  
  18.    head=n1;  
  19.    n1->next=n3;  
  20.    n3->next=n5;  
  21.    n5->next=n7;  
  22.    n7->next=n9;  
  23.    n9->next=NULL;  
  24.    return head;  
  25. }  
  26. Node* CreateList2()//创建一个有序的单链表2  
  27. {  
  28.    Node *head;  
  29.    Node *n2=new Node(2);  
  30.    Node *n4=new Node(4);  
  31.    Node *n6=new Node(6);  
  32.    Node *n8=new Node(8);  
  33.    head=n2;  
  34.    n2->next=n4;  
  35.    n4->next=n6;  
  36.    n6->next=n8;  
  37.    n8->next=NULL;  
  38.    return head;  
  39. }  
  40. void FreeList(Node *head)//将链表空间释放  
  41. {  
  42.     if(head==NULL)  
  43.     {  
  44.         return ;  
  45.     }  
  46.     else  
  47.     {  
  48.         Node *temp=head->next;  
  49.         delete head;  
  50.         head=temp;  
  51.         FreeList(head);  
  52.     }  
  53. }  
  54.   
  55. void VisitList(Node *head)//遍历链表中的元素,用递归的方法遍历  
  56. {  
  57.     if(head)  
  58.     {  
  59.         cout<<head->value<<"->";  
  60.         VisitList(head->next);  
  61.     }  
  62.     else  
  63.     {  
  64.         cout<<"null"<<endl;  
  65.     }  
  66. }  
  67. Node *ListMerge(Node *head1,Node *head2)  
  68. {  
  69.     if(!head1) return head2;  
  70.     if(!head2) return head1;  
  71.     Node *head=NULL;//合并后的头指针  
  72.     Node *p1=head1;//p1用于扫描链表1  
  73.     Node *p2=head2;//p2用于扫描链表2  
  74.     if(head1->value<head2->value)  
  75.     {  
  76.         head=head1;  
  77.         p1=head1->next;  
  78.     }  
  79.     else  
  80.     {  
  81.         head=head2;  
  82.         p2=head2->next;  
  83.     }  
  84.     Node *p=head;//p永远指向最新合并的结点  
  85.     while(p1 && p2)//如果循环停止，则p1或p2至少有一个为NULL  
  86.     {  
  87.         if(p1->value<p2->value)  
  88.         {  
  89.             p->next=p1;  
  90.             p1=p1->next;  
  91.         }  
  92.         else  
  93.         {  
  94.             p->next=p2;  
  95.             p2=p2->next;  
  96.         }  
  97.         p=p->next;  
  98.     }  
  99.     if(p1)//如果链1还没走完  
  100.     {  
  101.         p->next=p1;  
  102.     }  
  103.     else if(p2)//如果链2还没走完  
  104.     {  
  105.         p->next=p2;  
  106.     }  
  107.     return head;  
  108. }  
  109.   
  110. Node *ListMerge1(Node *head1,Node *head2)//采用递归的方法实现  
  111. {  
  112.     if(head1==NULL)  
  113.         return head2;  
  114.     if(head2==NULL)  
  115.         return head1;  
  116.     Node *head=NULL;  
  117.     if(head1->value < head2->value)  
  118.     {  
  119.         head=head1;  
  120.         head->next=ListMerge1(head1->next,head2);  
  121.     }  
  122.     else  
  123.     {  
  124.         head=head2;  
  125.         head->next=ListMerge1(head1,head2->next);  
  126.     }  
  127.     return head;  
  128. }  
  129. int main()  
  130. {  
  131.     Node *head1=CreateList1();  
  132.     Node *head2=CreateList2();  
  133.     cout<<"归并前"<<endl;  
  134.     cout<<"链表1:";  
  135.     VisitList(head1);  
  136.     cout<<"链表2:";  
  137.     VisitList(head2);  
  138.     cout<<"合并后的链表:";  
  139.     //Node *head=ListMerge(head1,head2);  
  140.     Node *head=ListMerge1(head1,head2);  
  141.     VisitList(head);  
  142.     FreeList(head);  
  143.     return 0;  
  144. }  

 

          测试结果如下：

技术分享

参考资料-------------《剑指offer》

算法题：合并两个有序的链表


联系
我们