2024/9/21 leetcode 21.合并两个有序链表 2.两数相加
目录
21.合并两个有序链表
题目描述
题目链接
解题思路与代码
2.两数相加
题目描述
题目链接
解题思路与代码
---------------------------------------------------------------------------
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均按 非递减顺序 排列
题目链接
21.合并两个有序链表
解题思路与代码
这题其实很简单。首先，我们创立一个虚拟头节点，作为返回结果的存储链表。然后我们使用的是双指针思路，两个链表进行比较，然后比较小的那一个结点放到我们创立的新头节点后面，同时将该指针向后移动一位，如图：
（初始状态）
（一次比较）
（二次比较）
（三次比较）
（四次比较）
（五次比较）
（六次比较）
（七次比较）
此时应该已经跳出循环了，所以执行这行代码，将剩下一段的合并到最终链表里面。
cur ->next = (list1 == NULL) ? list2 : list1;
最后我们发现nhead用于遍历链表存数据，然后res是我们一开始就建立的变量，最后只需要返回res->next就是最终结果。
（c++代码）
/**
* 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* nhead = new ListNode();
ListNode* cur = nhead;
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 nhead ->next;
}
};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- 题目数据保证列表表示的数字不含前导零
题目链接
2.两数相加
解题思路与代码
假设有这么两个初始链表，然后head是我们创建的结果链表的虚拟头节点。
解题思路：
本题其实就是一个用链表模拟加法的问题，涉及一个加法进位的问题，
比如看上图这个例子，换成数字加法就很好理解了。
3 5 9
9 9 0
3 + 9 余2进1
5 9
9 0
1
结果：2
5 + 9 + 1 余5进1
9
0
1
结果：2 5
0 + 1 + 9 余0进1
结果 2 5 0 1
按顺序存入链表就是最终结果
tem : 每次循环存储l1和l2对应结点的和（也可能只加一个结点，因为存在一个结点为空，另一个不为空的情况），t是存储上一次加法是否进位，进位用tem/10获取。
当前位结果用tem% 10获取。
后面就是简单的处理逻辑。
(c++代码)
/**
* 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) {
ListNode* head = new ListNode();
ListNode* res = head;
int t = 0;
while(l1 != NULL || l2 != NULL) {
int tem = t;
if(l1 != NULL) {
tem += l1 ->val;
l1 = l1 ->next;
}
if(l2 != NULL ) {
tem += l2 ->val;
l2 = l2 ->next;
}
int num = tem % 10;
t = tem / 10;
ListNode* node = new ListNode(num);
head ->next = node;
head = head ->next;
}
if(t == 1) head ->next = new ListNode(t);
return res ->next;
}
};欧克，这就是今天的力扣啦。