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

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

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

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入: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);
PHP常量类型
linux 10个top工具