題干
輸入兩個遞增排序的鏈表梢卸，合并這兩個鏈表并使新鏈表中的節(jié)點仍然使遞增排序的犀勒。例如輸入下圖中的鏈表1和鏈表2蕴纳，則合并之后的升序鏈表如鏈表3所示会油。鏈表節(jié)點定義如下：
class ListNode {
int val;
ListNode next;
}
鏈表1
graph LR
1-->3
3-->5
5-->7
鏈表2
graph LR
2-->4
4-->6
6-->8
鏈表3
graph LR
1-->2
2-->3
3-->4
4-->5
5-->6
6-->7
7-->8
解題思路
取出兩個鏈表的頭節(jié)點進行比較，取值小的的頭節(jié)點袱蚓，將其合并到最終鏈表的尾部钞啸，然后比較剩余節(jié)點構(gòu)成的鏈表的頭節(jié)點几蜻，一直比較的沒有可以比較的節(jié)點時終止喇潘。
代碼實現(xiàn)
<?php
class ListNode
{
private $val;
private $next;
public function __set($name, $value)
{
$this->$name = $value;
}
public function __get($name)
{
return $this->$name;
}
}
function getList1()
{
$node1 = new ListNode();
$node1->val = 1;
$node2 = new ListNode();
$node2->val = 3;
$node1->next = $node2;
$node3 = new ListNode();
$node3->val = 5;
$node2->next = $node3;
$node4 = new ListNode();
$node4->val = 7;
$node3->next = $node4;
return $node1;
}
function getList2()
{
$node1 = new ListNode();
$node1->val = 2;
$node2 = new ListNode();
$node2->val = 4;
$node1->next = $node2;
$node3 = new ListNode();
$node3->val = 6;
$node2->next = $node3;
$node4 = new ListNode();
$node4->val = 8;
$node3->next = $node4;
return $node1;
}
function mergeList($head1, $head2)
{
if ($head1 == null) {
return $head2;
}
if ($head2 == null) {
return $head1;
}
$mergeHead = null;
if ($head1->val < $head2->val) {
$mergeHead = $head1;
$mergeHead->next = mergeList($head1->next, $head2);
} else {
$mergeHead = $head2;
$mergeHead->next = mergeList($head1, $head2->next);
}
return $mergeHead;
}
var_dump(mergeList(getList1(), getList2()));
