Java教程

21. 合并两个有序链表(mergeTwoLists)

本文主要是介绍21. 合并两个有序链表(mergeTwoLists)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

题解：

查看代码 
/***
执行用时：4 ms, 在所有 PHP 提交中击败了92.74% 的用户
内存消耗：18.9 MB, 在所有 PHP 提交中击败了13.71% 的用户
通过测试用例：208 / 208
*/
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

        /**
        * @param ListNode $list1
        * @param ListNode $list2
        * @return ListNode
        */
   function mergeTwoLists($list1, $list2)
    {
        $res = null;
        $this->merge($list1, $list2, $res);
        return $res;
    }

    function merge($l1, $l2, &$node)
    {
        if (null == $l1 && null == $l2)
            return;

        $node = new ListNode();
        if (null == $l1) {
            $node->val = $l2->val;
            $this->merge(null, $l2->next, $node->next);
        } elseif (null == $l2) {
            $node->val = $l1->val;
            $this->merge($l1->next, null, $node->next);
        } elseif ($l1->val < $l2->val) {
            $node->val = $l1->val;
            $this->merge($l1->next, $l2, $node->next);
        } else {
            $node->val = $l2->val;
            $this->merge($l1, $l2->next, $node->next);
        }
    }
}
这篇关于21. 合并两个有序链表(mergeTwoLists)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航