合并两个有序链表/mergeTwoLists.php
<?php


/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution
{

    /**
     * 递归的方式
     * 我们直接将以上递归过程建模，首先考虑边界情况。
     * 特殊的，如果 l1 或者 l2 一开始就是 null ，那么没有任何操作需要合并，所以我们只需要返回非空链表。
     * 否则，我们要判断 l1 和 l2 哪一个的头元素更小，然后递归地决定下一个添加到结果里的值。
     * 如果两个链表都是空的，那么过程终止，所以递归过程最终一定会终止
     */
    function mergeTwoLists($l1, $l2)
    {
        if ($l1 == null) {
            return $l2;
        } else if ($l2 == null) {
            return $l1;
        } else if ($l1->val < $l2->val) {
            $l1->next = $this->mergeTwoLists($l1->next, $l2);
            return $l1;
        } else {
            $l2->next = $this->mergeTwoLists($l1, $l2->next);
            return $l2;
        }
    }

    function mergeTwoLists1($l1,$l2)
    {
        $prehead = new ListNode(-1);
        $prev = $prehead;
        while ($l1 != null && $l2 != null) {
            if ($l1->val <= $l2->val) {
                $prev->next = $l1;
                $l1 = $l1->next;
            } else {
                $prev->next = $l2;
                $l2 = $l2->next;
            }
            $prev = $prev->next;
        }
        $prev->next = $l1 == null ? $l2 : $l1;
        return $prehead->next;

    }

    function b($l1, $l2)
    {
        if ($l1 != null && $l2 != null) {
            if ($l1->val > $l2->val) {
                $temp = $l1;
                $l1 = $l2;
                $l2 = $temp;
            }
            $l1->next = $this->mergeTwoLists($l1->next, $l2);
        }
        return $l1 or $l2;

    }
}