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

问题

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

解决思路

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

实现代码：

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. }

Tags: PHP合并排序链表

分享到：