剑指Offer - PHP合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
代码
<?php
/*class ListNode{
var $val;
var $next = NULL;
function __construct($x){
$this->val = $x;
}
}*/
/**
* 递归
*/
function Merge($pHead1, $pHead2)
{
if($pHead1 == null) return $pHead2; // 如果链表1没有节点了，则返回链表2
if($pHead2 == null) return $pHead1; // 如果链表2没有节点了，则返回链表1
$newHead = new ListNode(null); // 实例新的链表头
// 如果链表1的节点值 <= 链表2的节点值，则将链表1节点赋值给$newHead，并且链表1往下个节点移动
if($pHead1->val <= $pHead2->val){
$newHead = $pHead1;
$newHead->next = Merge($pHead1->next,$pHead2);
}else {
// 如果链表1的节点值 > 链表2的节点值，则将链表2的节点值赋值给$newHead，并且链表2往下个节点移动
$newHead = $pHead2;
$newHead->next = Merge($pHead1, $pHead2->next);
}
// 返回最终的链表
return $newHead;
}
关于 LearnKu
粤公网安备 44030502004330号