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 <= 100
• l1 和 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;}
};

欧克，这就是今天的力扣啦。