題目敘述
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.
Return the head of the merged linked list.
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.
題目翻譯
有兩個排序序列 list1 和 list2，要將其合併成一個序列並且要是排序的。
解法解析
解法上就是依舊使用 Iteration 和 Recursion 的方式來處理，使用上 Iteration 的方式可以有更好的空間複雜度。
解法範例
Go
Recursion
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
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
var prehead ListNode = ListNode{}
var prev *ListNode = &prehead
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
}
return prehead.Next
}
JavaScript
Recursion
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
var mergeTwoLists = function (list1, list2) {
let prehead = new ListNode(0);
let prev = prehead;
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;
return prehead.next;
};
Kotlin
Recursion
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
class Solution {
fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
var prehead: ListNode? = ListNode(0)
var prev: ListNode? = prehead
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
return prehead?.next
}
}
PHP
Recursion
class Solution
{
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
class Solution
{
function mergeTwoLists($list1, $list2)
{
$prehead = new ListNode(0);
$prev = $prehead;
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;
return $prehead->next;
}
}
Python
Recursion
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
class Solution:
def mergeTwoLists(
self, list1: ListNode | None, list2: ListNode | None
) -> ListNode | None:
prehead = ListNode(-1)
prev = prehead
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
prev.next = list1 or list2
return prehead.next
Rust
Swift
Recursion
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
class Solution {
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
var prehead: ListNode? = ListNode(0)
var prev: ListNode? = prehead
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
return prehead?.next
}
}