本文实例讲述了PHP实现合并两个排序链表的方法。分享给大家供大家参考,具体如下:
问题
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
解决思路
简单的合并排序。由于两个数列本来就是递增的,所以每次将两个数列中较小的部分拿过来就可以了。
实现代码
</>code
- <?php
- /*class ListNode{
- var $val;
- var $next = NULL;
- function __construct($x){
- $this->val = $x;
- }
- }*/
- function Merge($pHead1, $pHead2)
- {
- if($pHead1 == NULL)
- return $pHead2;
- if($pHead2 == NULL)
- return $pHead1;
- $reHead = new ListNode();
- if($pHead1->val < $pHead2->val){
- $reHead = $pHead1;
- $pHead1 = $pHead1->next;
- }else{
- $reHead = $pHead2;
- $pHead2 = $pHead2->next;
- }
- $p = $reHead;
- while($pHead1&&$pHead2){
- if($pHead1->val <= $pHead2->val){
- $p->next = $pHead1;
- $pHead1 = $pHead1->next;
- $p = $p->next;
- }
- else{
- $p->next = $pHead2;
- $pHead2 = $pHead2->next;
- $p = $p->next;
- }
- }
- if($pHead1 != NULL){
- $p->next = $pHead1;
- }
- if($pHead2 != NULL)
- $p->next = $pHead2;
- return $reHead;
- }
php实现两表合并成新表并且有序排列的方法。
具体实现方法如下:
</>code
- <?php
- /**
- la (3,5,8,11)
- lb(2,6,8,9,11,15)
- 合并为lc,有序排列。
- 用php实现,不能用sort之类的函数!!!!
- **/
- class union {
- var $lista = array();
- var $listb = array();
- var $listc = array();
- function getlenght($arr) { //获得表长度
- return count($arr);
- }
- function getelement($arr, $n) { //获取表中第n个元素,返回
- return $e = $arr[$n] ? $arr[$n] : '';
- }
- function listinsert($arr, $e) { //表末尾插入元素
- $arr[] = $e;
- return $arr;
- }
- }
- $phpig = new union();
- $lista = $phpig->lista = array(3, 5, 8, 11);
- $listb = $phpig->listb = array(2, 6, 8, 9, 11, 15);
- $listc = $phpig->listc;
- $lena = $phpig->getlenght($lista); //取得表大小
- $lenb = $phpig->getlenght($listb);
- $i = $j = 0;
- while($i < $lena && $j < $lenb) {
- $ea = $phpig->getelement($lista, $i);
- $eb = $phpig->getelement($listb, $j);
- if($ea <= $eb) {
- $listc = $phpig->listinsert($listc, $ea);
- ++$i;
- } else {
- $listc = $phpig->listinsert($listc, $eb);
- ++$j;
- }
- }
- while($i < $lena) {
- $ea = $phpig->getelement($lista, $i);
- $listc = $phpig->listinsert($listc, $ea);
- ++$i;
- }
- while($j < $lenb) {
- $eb = $phpig->getelement($listb, $j);
- $listc = $phpig->listinsert($listc, $eb);
- ++$j;
- }
- print_r($listc);
- ?>
如对本文有疑问,请提交到交流论坛,广大热心网友会为你解答!! 点击进入论坛