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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!