您现在的位置: 365建站网 > 365文章 > PHP实现合并两个排序链表的代码

PHP实现合并两个排序链表的代码

文章来源:365jz.com     点击数:340    更新时间:2018-01-19 11:48   参与评论

本文实例讲述了PHP实现合并两个排序链表的方法。分享给大家供大家参考,具体如下:

问题

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

解决思路

简单的合并排序。由于两个数列本来就是递增的,所以每次将两个数列中较小的部分拿过来就可以了。

实现代码

</>code

  1. <?php
  2. /*class ListNode{
  3. var $val;
  4. var $next = NULL;
  5. function __construct($x){
  6. $this->val = $x;
  7. }
  8. }*/
  9. function Merge($pHead1, $pHead2)
  10. {
  11. if($pHead1 == NULL)
  12. return $pHead2;
  13. if($pHead2 == NULL)
  14. return $pHead1;
  15. $reHead = new ListNode();
  16. if($pHead1->val < $pHead2->val){
  17. $reHead = $pHead1;
  18. $pHead1 = $pHead1->next;
  19. }else{
  20. $reHead = $pHead2;
  21. $pHead2 = $pHead2->next;
  22. }
  23. $p = $reHead;
  24. while($pHead1&&$pHead2){
  25. if($pHead1->val <= $pHead2->val){
  26. $p->next = $pHead1;
  27. $pHead1 = $pHead1->next;
  28. $p = $p->next;
  29. }
  30. else{
  31. $p->next = $pHead2;
  32. $pHead2 = $pHead2->next;
  33. $p = $p->next;
  34. }
  35. }
  36. if($pHead1 != NULL){
  37. $p->next = $pHead1;
  38. }
  39. if($pHead2 != NULL)
  40. $p->next = $pHead2;
  41. return $reHead;
  42. }


php实现两表合并成新表并且有序排列的方法。

具体实现方法如下:

 

</>code

  1. <?php
  2. /**
  3. la (3,5,8,11)
  4. lb(2,6,8,9,11,15)
  5. 合并为lc,有序排列。
  6. 用php实现,不能用sort之类的函数!!!!
  7. **/
  8. class union {
  9.     var $lista = array();
  10.     var $listb = array();
  11.     var $listc = array();
  12.     
  13.     function getlenght($arr) { //获得表长度
  14.         return count($arr);
  15.     }
  16.     
  17.     function getelement($arr, $n) { //获取表中第n个元素,返回
  18.         return $e = $arr[$n] ? $arr[$n] : '';
  19.     }
  20.     
  21.     function listinsert($arr, $e) { //表末尾插入元素
  22.         $arr[] = $e;
  23.         return $arr;
  24.     }
  25. }
  26. $phpig = new union();
  27. $lista = $phpig->lista = array(3, 5, 8, 11);
  28. $listb = $phpig->listb = array(2, 6, 8, 9, 11, 15);
  29. $listc = $phpig->listc;
  30. $lena = $phpig->getlenght($lista); //取得表大小
  31. $lenb = $phpig->getlenght($listb);
  32. $i = $j = 0;
  33. while($i < $lena && $j < $lenb) {
  34.     $ea = $phpig->getelement($lista, $i);
  35.     $eb = $phpig->getelement($listb, $j);
  36.     if($ea <= $eb) {
  37.         $listc = $phpig->listinsert($listc, $ea);
  38.         ++$i;
  39.     } else {
  40.         $listc = $phpig->listinsert($listc, $eb);
  41.         ++$j;
  42.     }
  43. }
  44. while($i < $lena) {
  45.     $ea = $phpig->getelement($lista, $i);
  46.     $listc = $phpig->listinsert($listc, $ea);
  47.     ++$i;
  48. }
  49. while($j < $lenb) {
  50.     $eb = $phpig->getelement($listb, $j);
  51.     $listc = $phpig->listinsert($listc, $eb);
  52.     ++$j;
  53. }
  54. print_r($listc);
  55. ?>

 

 

如对本文有疑问,请提交到交流论坛,广大热心网友会为你解答!! 点击进入论坛

发表评论 (340人查看0条评论)
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
昵称:
最新评论
------分隔线----------------------------

快速入口

· 365软件
· 杰创官网
· 建站工具
· 网站大全

其它栏目

· 建站教程
· 365学习

业务咨询

· 技术支持
· 服务时间:9:00-18:00
365建站网二维码

Powered by 365建站网 RSS地图 HTML地图

copyright © 2013-2024 版权所有 鄂ICP备17013400号