题解 | #合并两个排序的链表#

<?php

/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
function Merge( $pHead1 ,  $pHead2 )
{
    // write code here
    $ret = $pHead1;
    $pre = null;
    while($pHead1 != null && $pHead2 != null){
        if($pHead1->val >= $pHead2->val && ($pre == null || $pre->val <= $pHead2->val)){
            $insert = new ListNode($pHead2->val);
            if($pre != null){
                $pre->next = $insert;
            }else{
                $ret = $insert;
            }
            $insert->next = $pHead1;
            $pre = $insert;
            $pHead2 = $pHead2->next;
        }else{
            $pre = $pHead1;
            $pHead1 = $pHead1->next;
        }
    }
    if($pHead1 == null){
        $pre->next = $pHead2;
    }
    return $ret;
}

p2往p1里插，p1有两个指针，pHead1 >= pHead2 && pre <= pHead2，即pHead2的那个值插入p1。注意判断pre是null的情况，以及如果pHead1指向尾部null了，phead2还没有结束，可以把剩下的全部附在p1尾部