代码拉取完成，页面将自动刷新
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into 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:
[0, 50].-100 <= Node.val <= 100list1 and list2 are sorted in non-decreasing order.First, we judge whether the linked lists $l_1$ and $l_2$ are empty. If one of them is empty, we return the other linked list. Otherwise, we compare the head nodes of $l_1$ and $l_2$:
The time complexity is $O(m + n)$, and the space complexity is $O(m + n)$. Here, $m$ and $n$ are the lengths of the two linked lists respectively.
# 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: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
if list1 is None or list2 is None:
return list1 or list2
if list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val <= list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (!list1) return list2;
if (!list2) return list1;
if (list1->val <= list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
/**
* 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
} else {
list2.Next = mergeTwoLists(list1, list2.Next)
return list2
}
}
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
if (list1 == null || list2 == null) {
return list1 || list2;
}
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn merge_two_lists(
list1: Option<Box<ListNode>>,
list2: Option<Box<ListNode>>
) -> Option<Box<ListNode>> {
match (list1, list2) {
(None, None) => None,
(Some(list), None) => Some(list),
(None, Some(list)) => Some(list),
(Some(mut list1), Some(mut list2)) => {
if list1.val < list2.val {
list1.next = Self::merge_two_lists(list1.next, Some(list2));
Some(list1)
} else {
list2.next = Self::merge_two_lists(Some(list1), list2.next);
Some(list2)
}
}
}
}
}
/**
* 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 || !list2) {
return list1 || list2;
}
if (list1.val <= list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
};
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (list1 != null && list2 != null)
{
if (list1.val <= list2.val)
{
cur.next = list1;
list1 = list1.next;
}
else
{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 == null ? list2 : list1;
return dummy.next;
}
}
# Definition for singly-linked list.
# class ListNode
# attr_accessor :val, :next
# def initialize(val = 0, _next = nil)
# @val = val
# @next = _next
# end
# end
# @param {ListNode} list1
# @param {ListNode} list2
# @return {ListNode}
def merge_two_lists(list1, list2)
dummy = ListNode.new()
cur = dummy
while list1 && list2
if list1.val <= list2.val
cur.next = list1
list1 = list1.next
else
cur.next = list2
list2 = list2.next
end
cur = cur.next
end
cur.next = list1 || list2
dummy.next
end
We can also use iteration to implement the merging of two sorted linked lists.
First, we define a dummy head node $dummy$, then loop through the two linked lists, compare the head nodes of the two linked lists, add the smaller node to the end of $dummy$, until one of the linked lists is empty, then add the remaining part of the other linked list to the end of $dummy$.
Finally, return $dummy.next$.
The time complexity is $O(m + n)$, where $m$ and $n$ are the lengths of the two linked lists respectively. Ignoring the space consumption of the answer linked list, the space complexity is $O(1)$.
# 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: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
curr = dummy
while list1 and list2:
if list1.val <= list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
curr.next = list1 or list2
return dummy.next
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode 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;
}
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummy = new ListNode();
ListNode* curr = dummy;
while (list1 && list2) {
if (list1->val <= list2->val) {
curr->next = list1;
list1 = list1->next;
} else {
curr->next = list2;
list2 = list2->next;
}
curr = curr->next;
}
curr->next = list1 ? list1 : list2;
return dummy->next;
}
};
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dummy := &ListNode{}
curr := dummy
for list1 != nil && list2 != nil {
if list1.Val <= list2.Val {
curr.Next = list1
list1 = list1.Next
} else {
curr.Next = list2
list2 = list2.Next
}
curr = curr.Next
}
if list1 != nil {
curr.Next = list1
} else {
curr.Next = list2
}
return dummy.Next
}
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
const dummy = new ListNode(0);
let cur = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 || list2;
return dummy.next;
}
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn merge_two_lists(
mut list1: Option<Box<ListNode>>,
mut list2: Option<Box<ListNode>>
) -> Option<Box<ListNode>> {
let mut new_list = ListNode::new(0);
let mut cur = &mut new_list;
while list1.is_some() && list2.is_some() {
let (l1, l2) = (list1.as_deref_mut().unwrap(), list2.as_deref_mut().unwrap());
if l1.val < l2.val {
let next = l1.next.take();
cur.next = list1.take();
list1 = next;
} else {
let next = l2.next.take();
cur.next = list2.take();
list2 = next;
}
cur = cur.next.as_deref_mut().unwrap();
}
cur.next = list1.or(list2);
new_list.next
}
}
/**
* 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) {
const dummy = new ListNode();
let curr = dummy;
while (list1 && list2) {
if (list1.val <= list2.val) {
curr.next = list1;
list1 = list1.next;
} else {
curr.next = list2;
list2 = list2.next;
}
curr = curr.next;
}
curr.next = list1 || list2;
return dummy.next;
};
# Definition for singly-linked list.
# class ListNode {
# public $val;
# public $next;
# public 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) {
$dummy = new ListNode(0);
$current = $dummy;
while ($list1 != null && $list2 != null) {
if ($list1->val <= $list2->val) {
$current->next = $list1;
$list1 = $list1->next;
} else {
$current->next = $list2;
$list2 = $list2->next;
}
$current = $current->next;
}
if ($list1 != null) {
$current->next = $list1;
} elseif ($list2 != null) {
$current->next = $list2;
}
return $dummy->next;
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。