题记：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
题目来源：
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnnbp2/
来源：力扣（LeetCode）
解题方法：
一：
因为链表是升序的，我们只需要遍历每个链表的头，比较一下哪个小就把哪个链表的头拿出来放到新的链表中，一直这样循环，直到有一个链表为空，然后我们再把另一个不为空的链表挂到新的链表中。
我们就以3→4→7→9和2→5→6两个链表来画个图看一下是怎么合并的。
看明白了上面的图，代码就很容易写了，我们来看一下非递归的代码
public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {
//下面4行是空判断
if (linked1 == null)
return linked2;
if (linked2 == null)
return linked1;
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (linked1 != null && linked2 != null) {
//比较一下，哪个小就把哪个放到新的链表中
if (linked1.val <= linked2.val) {
curr.next = linked1;
linked1 = linked1.next;
} else {
curr.next = linked2;
linked2 = linked2.next;
}
curr = curr.next;
}
//然后把那个不为空的链表挂到新的链表中
curr.next = linked1 == null ? linked2 : linked1;
return dummy.next;
}
转换为PHP代码为：
/**
* 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) {
//进行空判断
if($list1 == null){
return $list2;
}
if($list2 == null){
return $list1;
}
$dummy = new ListNode(0);
$curr = $dummy;
while($list1 != null && $list2 != null){
//比较，哪个小就把哪个放到新的链表中
if($list1->val <= $list2->val){
$curr->next = $list1;
$list1 = $list1->next;
}else{
$curr->next = $list2;
$list2 = $list2->next;
}
$curr = $curr->next;
}
//此时至少有一个链表为空了，然后把不为空的链表挂到新的链表中
$curr->next = $list1 == null ? $list2 : $list1;
return $dummy->next;
}
}
二：递归方法
我们还可以把它改为递归的形式，看下递归的代码
public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {
if (linked1 == null)
return linked2;
if (linked2 == null)
return linked1;
if (linked1.val < linked2.val) {
linked1.next = mergeTwoLists(linked1.next, linked2);
return linked1;
} else {
linked2.next = mergeTwoLists(linked1, linked2.next);
return linked2;
}
}
转换为PHP代码为：
/**
* 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) {
//进行空判断
if($list1 == null){
return $list2;
}
if($list2 == null){
return $list1;
}
if($list1->val <= $list2->val){
//把list1的头结点给摘除
$list1->next = $this->mergeTwoLists($list1->next,$list2);
return $list1;
}else{
//把list2的头结点给摘除
$list2->next = $this->mergeTwoLists($list1,$list2->next);
return $list2;
}
}
}
递归代码我们还可以再改一下
public ListNode mergeTwoLists(ListNode linked1, ListNode linked2) {
//只要有一个为空，就返回另一个
if (linked1 == null || linked2 == null)
return linked2 == null ? linked1 : linked2;
//把小的赋值给first
ListNode first = (linked2.val < linked1.val) ? linked2 : linked1;
first.next = mergeTwoLists(first.next, first == linked1 ? linked2 : linked1);
return first;
}
转换为PHP代码为：文章来源：https://www.toymoban.com/news/detail-725034.html
function mergeTwoLists($list1,$list2){
//只要有一个为空，就返回另一个
if($list1 == null || $list2 == null){
return $list2 == null ? $list1 : $list2;
}
//把小的赋值给first
$first = ($list2->val < $list1->val) ? $list2 : $list1;
$first->next = $this->mergeTwoLists($first->next, $first == $list1 ? $list2 : $list1);
return $first;
}
方法来源：
作者：数据结构和算法
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnnbp2/?discussion=1mcRST
来源：力扣（LeetCode）文章来源地址https://www.toymoban.com/news/detail-725034.html
到了这里，关于合并两个有序链表，将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
