一道百度算法面试题：链表合并

在程序猿面试的过程中，都会现场考一些算法题，简单可能就是一个排序算法，一个查找算法，复杂可能就是一个应用，优秀的面试官对于简单就考察细节，复杂就只关注核心思想。

最近一个朋友参加百度的面试，要求实现下面的一个简单算法：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

PHP实现：

<?php
//方法一：系统函数, 过滤简单，没有实现考官的考点
/*
$arr1 = [1,2,4,];
$arr2 = [1,3,4,];

foreach($arr2 as $item) {
    $arr1[] = $item;
}

asort($arr1);

print_r($arr1);
 */

//方法二： 模拟链表实现
$arr1 = [1,2,4,];
$arr2 = [1,3,4,];

$list = [];

$index = 0;

$len1 = count($arr1);
$len2 = count($arr2);

for($i=0, $j = 0; $i < $len1 && $j < $len2; ) {
    if ($arr1[$i] < $arr2[$j])  {
        $list[$index] = $arr1[$i];
        $index++;
        $i++;
    } else {
        $list[$index] = $arr2[$j];
        $index++;
        $j++;
    }
}

$left = $i < $len1 ? $arr1 : $arr2;
$k = $i < $len1 ? $i : $j;

for(;$k < count($left); $k++) {
    $list[$index] = $left[$k];
    $index++;
}
print_r($list);