# 21. Merge Two Sorted Lists

## 題目敘述

You are given the heads of two sorted linked `lists` list1 and `list2`.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

``````Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
``````

Example 2:

``````Input: list1 = [], list2 = []
Output: []
``````

Example 3:

``````Input: list1 = [], list2 = [0]
Output: [0]
``````

Constraints:

• The number of nodes in both lists is in the range `[0, 50]`.
• `-100 <= Node.val <= 100`
• Both `list1` and `list2` are sorted in non-decreasing order.

## 解法解析

### 解法範例

#### Go

##### Recursion
``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
if list1 == nil {
return list2
}
if list2 == nil {
return list1
}
if list1.Val < list2.Val {
list1.Next = mergeTwoLists(list1.Next, list2)
return list1
}
list2.Next = mergeTwoLists(list1, list2.Next)
return list2
}
``````
##### Iteration
``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {

for list1 != nil && list2 != nil {
if list1.Val < list2.Val {
prev.Next = list1
list1 = list1.Next
} else {
prev.Next = list2
list2 = list2.Next
}
prev = prev.Next
}
if list1 != nil {
prev.Next = list1
} else {
prev.Next = list2
}
}
``````

#### JavaScript

##### Recursion
``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function (list1, list2) {
if (list1 === null) {
return list2;
}
if (list2 === null) {
return list1;
}
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}
list2.next = mergeTwoLists(list1, list2.next);
return list2;
};
``````
##### Iteration
``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function (list1, list2) {

while (list1 !== null && list2 !== null) {
if (list1.val < list2.val) {
prev.next = list1;
list1 = list1.next;
} else {
prev.next = list2;
list2 = list2.next;
}
prev = prev.next;
}

prev.next = list1 || list2;
};
``````

#### Kotlin

##### Recursion
``````/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* class ListNode(var `val`: Int) {
*     var next: ListNode? = null
* }
*/
class Solution {
fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
return when {
list1 == null -> list2
list2 == null -> list1
list1.`val` < list2.`val` -> {
list1.next = mergeTwoLists(list1.next, list2)
list1
}
else -> {
list2.next = mergeTwoLists(list1, list2.next)
list2
}
}
}
}
``````
##### Iteration
``````/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* class ListNode(var `val`: Int) {
*     var next: ListNode? = null
* }
*/
class Solution {
fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {

var l1: ListNode? = list1
var l2: ListNode? = list2
while (l1 != null && l2 != null) {
if (l1.`val` <= l2.`val`) {
prev?.next = l1
l1 = l1.next
} else {
prev?.next = l2
l2 = l2.next
}
prev = prev?.next
}
prev?.next = if (l1 != null) l1 else l2
}
}
``````

#### PHP

##### Recursion
``````/**
* 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 (is_null(\$list1)) {
return \$list2;
}
if (is_null(\$list2)) {
return \$list1;
}
if (\$list1->val <= \$list2->val) {
\$list1->next = \$this->mergeTwoLists(\$list1->next, \$list2);
return \$list1;
}
\$list2->next = \$this->mergeTwoLists(\$list1, \$list2->next);
return \$list2;
}
}
``````
##### Iteration
``````/**
* 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)
{

while (!is_null(\$list1) && !is_null(\$list2)) {
if (\$list1->val <= \$list2->val) {
\$prev->next = \$list1;
\$list1 = \$list1->next;
} else {
\$prev->next = \$list2;
\$list2 = \$list2->next;
}
\$prev = \$prev->next;
}
\$prev->next = \$list1 ?? \$list2;
}
}
``````

#### Python

##### Recursion
``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def mergeTwoLists(
self, list1: ListNode | None, list2: ListNode | None
) -> ListNode | None:
if list1 is None:
return list2
if list2 is None:
return list1
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
``````
##### Iteration
``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def mergeTwoLists(
self, list1: ListNode | None, list2: ListNode | None
) -> ListNode | None:
# maintain an unchanging reference to node ahead of the return node.

while list1 and list2:
if list1.val <= list2.val:
prev.next = list1
list1 = list1.next
else:
prev.next = list2
list2 = list2.next
prev = prev.next

# At least one of list1 and list2 can still have nodes at this point, so connect
# the non-null list to the end of the merged list.
prev.next = list1 or list2

``````

#### Rust

``````
``````

#### Swift

##### Recursion
``````/**
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init() { self.val = 0; self.next = nil; }
*     public init(_ val: Int) { self.val = val; self.next = nil; }
*     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
guard list1 != nil else {
return list2
}
guard list2 != nil else {
return list1
}

var result: ListNode? = nil
if list1!.val < list2!.val {
result = list1
result!.next = mergeTwoLists(list1!.next, list2)
} else {
result = list2
result!.next = mergeTwoLists(list1, list2!.next)
}
return result
}
}
``````
##### Iteration
``````/**
* public class ListNode {
*     public var val: Int
*     public var next: ListNode?
*     public init() { self.val = 0; self.next = nil; }
*     public init(_ val: Int) { self.val = val; self.next = nil; }
*     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {

var l1: ListNode? = list1
var l2: ListNode? = list2
while l1 != nil && l2 != nil {
if l1!.val <= l2!.val {
prev?.next = l1
l1 = l1?.next
} else {
prev?.next = l2
l2 = l2?.next
}

prev = prev?.next
}

prev?.next = (l1 == nil) ? l2 : l1