目标

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路

1.链表的第一解决方案就是递归，返回当前两个链表合并之后的头节点(每一层都返回排序好的链表头，就是永远是第一个的那个节点) 推荐此方法

public function mergeTwoLists($list1,$list2)
{
    if ($list1 === null) return $list2;
    if ($list2 === null) return $list1;

    if ($list1->val < $list2->val){
        $list1->next = $this->mergeTwoLists($list1->next, $list2);
        return $list1;
    } else {
        $list2->next = $this->mergeTwoLists($list1, $list2->next);
        return $list2;
    }
}

2.迭代法，不推荐

public function mergeTwoLists1($list1,$list2)
{
    $dummyHead = new ListNode();//这个永远都会指向链表头部
    $cur = $dummyHead;//防止指针移动到最后一位无法操作数据
    while($list1 !== null && $list2 !== null){
        if ($list1->val <= $list2->val){
            $cur->next = $list1;
            $list1 = $list1->next;
        } else {
            $cur->next = $list2;
            $list2 = $list2->next;
        }
        $cur = $cur->next;
    }

    if ($list1 !== null) {
        $cur->next = $list1;//list1在while里面已经重新赋值过了
    } elseif ($list2 !== null){
        $cur->next = $list2;//list2在while里面已经重新赋值过了
    }
    return $dummyHead->next;
}

public function abc()
{
    $list1=[1,2,4];
    $list2=[1,3,4];
    $list1=init($list1);
    $list2=init($list2);
    $res  = $this->mergeTwoLists1($list1,$list2);
    halt($res);
}


/**
 * 初始化链表
 * @param array $data 链表中要保存的数据，这里以数组为参考
 * @return LinkedList 链表数据
 */
function init(array $data)
{
    // 初始化 一般会让第一个结点不包含任何数据，仅仅是做为一个空的结点来指向第一个有数据的结点
    $list = createLinkedList($data);
    $r = $list;
    foreach ($data as $key => $value) {
        $link = new LinkedList();

        $link->val = $value;
        $link->next = null;
        $r->next = $link;
        $r = $link;
    }
    return $list;
}


/**
 * 生成链表
 */
function createLinkedList($data)
{
    $list = new LinkedList();
    $list->val = null;
    $list->next = null;
    return $list;
}

扩展

//链表与数组的不同：
//1.规定好数组（可储存的字节）之后，多出来的字节就必须从内存新申请一个数组来容纳全部字节。而链表则是随机分散在内存里面，链表只知道自己存放的数据和自己的下一个数据是谁，链表的节点可以是离散的
//2.数组只要知道数组下标之后，可以直接得到自己想要的数据，而链表却需要一个一个数下去才知道对应的节点数据