leetcode-链表篇4
leetcode-2
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]提示：
- 每个链表中的节点数在范围
[1, 100]内0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
思路：简单题，记住进位的控制就行
/**
* 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 *res = new ListNode(-1);
int tmp = 0;
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// if(!l1) {
// return l2;
// }
// if(!l2) {
// return l1;
// }
// int tmp=0;
// auto pre=new ListNode(-1);
// auto res = pre;
// while(l1 || l2 || tmp>0) {
// int fir = 0, sec = 0;
// if(l1) {
// fir = l1->val;
// l1 = l1->next;
// }
// if(l2) {
// sec = l2->val;
// l2 = l2->next;
// }
// auto sum = fir + sec + tmp;
// tmp = (sum / 10);
// auto val = (sum % 10);
// auto new_node = new ListNode(val);
// res->next = new_node;
// res = new_node;
// }
// res->next = nullptr;
// return pre->next;
if(!l1 && !l2 && !tmp) {
return nullptr;
}
auto fir = l1 ? l1->val : 0;
auto sec = l2 ? l2->val : 0;
auto sum = fir + sec + tmp;
tmp = sum / 10;
auto val = sum % 10;
auto node = new ListNode(val);
node->next = addTwoNumbers(l1?l1->next:l1, l2?l2->next:l2);
return node;
}
};leetcode-445
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4] 输出：[7,8,0,7]示例2：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7]示例3：
输入：l1 = [0], l2 = [0] 输出：[0]提示：
- 链表的长度范围为
[1, 100]0 <= node.val <= 9- 输入数据保证链表代表的数字无前导 0
进阶：如果输入链表不能翻转该如何解决？
思路：和刚才的题目相反。既然需要倒着加，我们自然而然的就想到一个数据结构：栈
/**
* 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<ListNode*>s1;
stack<ListNode*>s2;
while(l1 || l2) {
if(l1) {
s1.push(l1);
l1 = l1->next;
}
if(l2) {
s2.push(l2);
l2 = l2->next;
}
}
int tmp = 0;
auto pre = new ListNode(-1);
pre->next = nullptr;
while(!s1.empty() || !s2.empty() || tmp) {
int fir=0, sec=0;
if(!s1.empty()) {
fir = s1.top()->val;
s1.pop();
}
if(!s2.empty()) {
sec = s2.top()->val;
s2.pop();
}
auto sum = fir + sec + tmp;
tmp = sum / 10;
auto val = sum % 10;
auto node = new ListNode(val);
auto next = pre->next;
pre->next = node;
node->next = next;
}
return pre->next;
}
};leetcode-21
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]示例 2：
输入：l1 = [], l2 = [] 输出：[]示例 3：
输入：l1 = [], l2 = [0] 输出：[0]提示：
- 两个链表的节点数目范围是
[0, 50]-100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
思路：和两个链表相加差不多，都是遍历就可以
/**
* 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) {
auto pre = new ListNode(-1);
auto res = pre;
while (list1 && list2) {
if (list1->val >= list2->val) {
pre->next = list2;
list2 = list2->next;
} else {
pre->next = list1;
list1 = list1->next;
}
pre = pre->next;
}
pre->next = list1 ? list1 : list2;
return res->next;
}
};leetcode-23
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6示例 2：
输入：lists = [] 输出：[]示例 3：
输入：lists = [[]] 输出：[]提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
思路：使用优先级队列就可以
/**
* 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:
struct cmp {
bool operator()(ListNode* a, ListNode* b) { return a->val > b->val; }
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
for (auto val : lists) {
if(!val) {
continue;
}
pq.push(val);
}
auto pre = new ListNode(-1);
auto res = pre;
while (!pq.empty()) {
auto curr = pq.top();
pq.pop();
if (!curr) {
continue;
}
res->next = curr;
res = res->next;
if (res->next) {
pq.push(res->next);
}
}
res->next = nullptr;
return pre->next;
}
};