ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > IT综合 > 算法搜狗笔试题链表合并

算法搜狗笔试题链表合并

IT综合 作者：dongyu2013 时间：2014-04-26 10:04:42 0 删除 编辑
实现一个队链表排序的算法，C/C++可以使用std::list，Java使用LinkedList
要求先描述算法，然后再实现，算法效率尽可能高效。
主要考察链表的归并排序。
要点：需要使用快、慢指针的方法，找到链表的的中间节点，然后进行二路归并排序
[cpp] view plaincopy
  1. typedef struct LNode  
  2. {  
  3.     int data;  
  4.     struct LNode *next;  
  5. }LNode , *LinkList;  
  6.   
  7. // 对两个有序的链表进行递归的归并  
  8. LinkList MergeList_recursive(LinkList head1 , LinkList head2)  
  9. {  
  10.     LinkList result;  
  11.     if(head1 == NULL)  
  12.         return head2;  
  13.     if(head2 == NULL)  
  14.         return head1;  
  15.     if(head1->data < head2->data)  
  16.     {  
  17.         result = head1;  
  18.         result->next = MergeList_recursive(head1->next , head2);  
  19.     }  
  20.     else  
  21.     {  
  22.         result = head2;  
  23.         result->next = MergeList_recursive(head1 , head2->next);  
  24.     }  
  25.     return result;  
  26. }  
  27.   
  28. // 对两个有序的链表进行非递归的归并  
  29. LinkList MergeList(LinkList head1 , LinkList head2)  
  30. {  
  31.     LinkList head , result = NULL;  
  32.     if(head1 == NULL)  
  33.         return head2;  
  34.     if(head2 == NULL)  
  35.         return head1;  
  36.     while(head1 && head2)  
  37.     {  
  38.         if(head1->data < head2->data)  
  39.         {  
  40.             if(result == NULL)  
  41.             {  
  42.                 head = result = head1;  
  43.                 head1 = head1->next;  
  44.             }  
  45.             else  
  46.             {  
  47.                 result->next = head1;  
  48.                 result = head1;  
  49.                 head1 = head1->next;  
  50.             }  
  51.         }  
  52.         else  
  53.         {  
  54.             if(result == NULL)  
  55.             {  
  56.                 head = result = head2;  
  57.                 head2 = head2->next;  
  58.             }  
  59.             else  
  60.             {  
  61.                 result->next = head2;  
  62.                 result = head2;  
  63.                 head2 = head2->next;  
  64.             }  
  65.         }  
  66.     }  
  67.     if(head1)  
  68.         result->next = head1;  
  69.     if(head2)  
  70.         result->next = head2;  
  71.     return head;  
  72. }  
  73.   
  74. // 归并排序，参数为要排序的链表的头结点，函数返回值为排序后的链表的头结点  
  75. LinkList MergeSort(LinkList head)  
  76. {  
  77.     if(head == NULL)  
  78.         return NULL;  
  79.     LinkList r_head , slow , fast;  
  80.     r_head = slow = fast = head;  
  81.   
  82.     // 找链表中间节点的两种方法  
  83.     /* 
  84.     while(fast->next != NULL) 
  85.     { 
  86.         if(fast->next->next != NULL) 
  87.         { 
  88.             slow = slow->next; 
  89.             fast = fast->next->next; 
  90.         } 
  91.         else 
  92.             fast = fast->next; 
  93.     }*/  
  94.   
  95.     while(fast->next != NULL && fast->next->next != NULL)  
  96.     {  
  97.         slow = slow->next;  
  98.         fast = fast->next->next;  
  99.     }  
  100.       
  101.     if(slow->next == NULL)    // 链表中只有一个节点  
  102.         return r_head;  
  103.     fast = slow->next;  
  104.     slow->next = NULL;  
  105.     slow = head;  
  106.   
  107.     // 函数MergeList是对两个有序链表进行归并，返回值是归并后的链表的头结点  
  108.     //r_head = MergeList_recursive(MergeSort(slow) , MergeSort(fast));  
  109.     r_head = MergeList(MergeSort(slow) , MergeSort(fast));  
  110.     return r_head;  
  111. }  

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29012686/viewspace-1149844/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： 算法搜狗笔试题加减法
下一篇： 算法寻找数组中的第二大数
请登录后发表评论 登录
全部评论
dongyu2013

注册时间：2013-12-25

  • 博文量
    263
  • 访问量
    238062

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593