PHP实现合并两个排序链表的方法
本文实例讲述了PHP实现合并两个排序链表的方法。分享给大家供大家参考，具体如下：
问题
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解决思路
简单的合并排序，由于两个数列本来就是递增的，所以每次将两个数列中较小的部分拿过来就可以了。
实现代码：
- <?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;
- }