《剑指Offer》-25.合并两个排序的链表

题干

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然使递增排序的。例如输入下图中的链表1和链表2，则合并之后的升序链表如链表3所示。链表节点定义如下：

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

解题思路

取出两个链表的头节点进行比较，取值小的的头节点，将其合并到最终链表的尾部，然后比较剩余节点构成的链表的头节点，一直比较的没有可以比较的节点时终止。

代码实现

<?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()));