LeetCode Solution, Easy, 21. Merge Two Sorted Lists
合併兩個排序序列
Published
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.
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
list1andlist2are sorted in non-decreasing order.
題目翻譯
有兩個排序序列 list1 和 list2，要將其合併成一個序列並且要是排序的。
解法解析
解法上就是依舊使用 Iteration 和 Recursion 的方式來處理，使用上 Iteration 的方式可以有更好的空間複雜度。
解法範例
Go
Recursion
/**
* Definition for singly-linked list.
* 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
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
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
/**
* Definition for singly-linked list.
* 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
/**
* Definition for singly-linked list.
* 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) {
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
/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* 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`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
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
/**
* 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)
{
$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
# 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.
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
# 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
return prehead.next
Rust
Swift
Recursion
/**
* Definition for singly-linked list.
* 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
/**
* Definition for singly-linked list.
* 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 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
}
}