JavaScript (Рекурсивное)
class Solution {
mergeTwoLists(list1, list2) {
if (!list1) {
return list2;
}
if (!list2) {
return list1;
}
if (list1.val <= list2.val) {
list1.next = this.mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = this.mergeTwoLists(list1, list2.next);
return list2;
}
}
}
JavaScript (Итеративное)
class Solution {
mergeTwoLists(list1, list2) {
const dummy = new ListNode();
let current = dummy;
while (list1 && list2) {
if (list1.val <= list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
current.next = list1 || list2;
return dummy.next;
}
}
Java (Итеративное)
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode 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;
}
current.next = list1 != null ? list1 : list2;
return dummy.next;
}
}
Java (Рекурсивное)
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;
}
}
}
Python (Рекурсивное)
# 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 not list1:
return list2
if not list2:
return list1
if list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
Python (Итеративное)
# 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()
current = dummy
while list1 and list2:
if list1.val <= list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
current.next = list1 or list2
return dummy.next
Сложность:
- Рекурсивное решение: Время — O(n + m), пространство — O(n + m) (из-за стека вызовов).
- Итеративное решение: Время — O(n + m), пространство — O(1)