Linked Lists Merge¶
Table of Contents¶
- 2. Add Two Numbers (Medium)
- 445. Add Two Numbers II (Medium)
- 2816. Double a Number Represented as a Linked List (Medium)
- 21. Merge Two Sorted Lists (Easy)
- 369. Plus One Linked List (Medium) 👑
- 1634. Add Two Polynomials Represented as Linked Lists (Medium) 👑
2. Add Two Numbers¶
"""
- Represent the sum of two numbers as a linked list.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
# Linked List
def add_two_numbers(
l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
carry, val = divmod(v1 + v2 + carry, 10)
cur.next = ListNode(val)
cur = cur.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
if carry:
cur.next = ListNode(val=carry)
return dummy.next
def test_add_two_numbers():
l1 = list_from_array([2, 4, 3])
l2 = list_from_array([5, 6, 4])
result = add_two_numbers(l1, l2)
assert list_to_array(result) == [7, 0, 8]
#include <cassert>
#include <vector>
using namespace std;
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* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* cur = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
if (l1) {
carry += l1->val;
l1 = l1->next;
}
if (l2) {
carry += l2->val;
l2 = l2->next;
}
cur->next = new ListNode(carry % 10);
cur = cur->next;
carry /= 10;
}
return dummy.next;
}
};
int main() {
Solution sol;
ListNode* l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
ListNode* l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
ListNode* result = sol.addTwoNumbers(l1, l2);
vector<int> expected = {7, 0, 8};
for (int val : expected) {
assert(result != nullptr && result->val == val);
result = result->next;
}
assert(result == nullptr); // End of list
return 0;
}
445. Add Two Numbers II¶
2816. Double a Number Represented as a Linked List¶
"""
- Given a number represented as a linked list, double it and return the resulting linked list.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def doubleIt(head: Optional[ListNode]) -> Optional[ListNode]:
def twice(node):
if not node:
return 0
doubled_value = node.val * 2 + twice(node.next)
node.val = doubled_value % 10
return doubled_value // 10
carry = twice(head)
if carry:
head = ListNode(val=carry, next=head)
return head
def test_doubleIt() -> None:
head = list_from_array([9, 9, 9])
assert (list_to_array(doubleIt(head))) == [1, 9, 9, 8]
21. Merge Two Sorted Lists¶
"""
- Task: Merge the two linked lists into one sorted list.
"""
from typing import Optional
from leetpattern.utils import ListNode
# Linked List
def merge_two_lists(
list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
if list1:
cur.next = list1
elif list2:
cur.next = list2
return dummy.next
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
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;
ListNode* cur = &dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2;
return dummy.next;
}
};
int main() {
Solution sol;
ListNode* list1 = new ListNode(1, new ListNode(2, new ListNode(4)));
ListNode* list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
ListNode* merged = sol.mergeTwoLists(list1, list2);
vector<int> res;
while (merged) {
res.push_back(merged->val);
merged = merged->next;
}
assert(res == std::vector<int>({1, 1, 2, 3, 4, 4}));
return 0;
}