对于想了解LeetCode剑指OfferII025.链表中的两数相加的读者，本文将是一篇不可错过的文章，我们将详细介绍链表表示的两个数相加，并且为您提供关于leetcode#2两数相加、LeetCod
对于想了解LeetCode 剑指 Offer II 025. 链表中的两数相加的读者，本文将是一篇不可错过的文章，我们将详细介绍链表表示的两个数相加，并且为您提供关于leetcode #2 两数相加、LeetCode 01两数之和&02两数相加、LeetCode 2. 两数相加、LeetCode 445. 两数相加 II的有价值信息。
本文目录一览：- LeetCode 剑指 Offer II 025. 链表中的两数相加（链表表示的两个数相加）
- leetcode #2 两数相加
- LeetCode 01两数之和&02两数相加
- LeetCode 2. 两数相加
- LeetCode 445. 两数相加 II
LeetCode 剑指 Offer II 025. 链表中的两数相加（链表表示的两个数相加）
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。
它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
图解:
解题思路:首先将链表翻转,然后将两个链表节点值相加.
具体代码如下:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 如果 l1 为 null,直接返回 l2 if(l1 == null){ return l2; } // 如果 l2 为 null,直接返回 l1 if(l2 == null){ return l1; } // 计算 l1 长度 int count1 = 0; for(ListNode node = l1;node != null;node = node.next){ count1 ++; } // 计算 l2 长度 int count2 = 0; for(ListNode node = l2;node != null;node = node.next){ count2 ++; } // l1 > l2; l1 < l2;l1 = l2 三种情况 int sub = count1 - count2; ListNode newHead = new ListNode(-1); ListNode l3 = newHead; // 翻转链表 l1 = reverse(l1); l2 = reverse(l2); if(sub == 0){ // l1,l2 长度相同 // l1 = reverse(l1); // l2 = reverse(l2); int rem = 0; // l1 与 l2 长度相等 while(l1 != null && l2 != null){ int num = l1.val + l2.val + rem; ListNode node = new ListNode(num % 10); rem = num / 10; l3.next = node; l1 = l1.next; l2 = l2.next; l3 = l3.next; } if(rem == 1){ l3.next = new ListNode(1); } l3 = reverse(newHead.next); return l3; }else if(sub > 0){ // l1 的长度大于 l2 ListNode tmpL2 = l2; while(tmpL2.next != null){ tmpL2 = tmpL2.next; } for (int i = 0; i < sub; i++) { ListNode node = new ListNode(0); tmpL2.next = node; tmpL2 = tmpL2.next; } // l1,l2节点数相同 int rem = 0; while(l1 != null && l2 != null){ int num = l1.val + l2.val + rem; ListNode node = new ListNode(num % 10); rem = num / 10; l3.next = node; l1 = l1.next; l2 = l2.next; l3 = l3.next; } if(rem == 1){ l3.next = new ListNode(1); } l3 = reverse(newHead.next); return l3; }else{ // l1 的长度大于 l2 ListNode tmpL1 = l1; while(tmpL1.next != null){ tmpL1 = tmpL1.next; } for (int i = 0; i < -sub; i++) { ListNode node = new ListNode(0); tmpL1.next = node; tmpL1 = tmpL1.next; } // l1,l2节点数相同 int rem = 0; while(l1 != null && l2 != null){ int num = l1.val + l2.val + rem; ListNode node = new ListNode(num % 10); rem = num / 10; l3.next = node; l1 = l1.next; l2 = l2.next; l3 = l3.next; } if(rem == 1){ l3.next = new ListNode(1); } l3 = reverse(newHead.next); return l3; } } // 反转链表 private ListNode reverse(ListNode head) { ListNode prev = null; ListNode cur = head; while(cur != null){ ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; }
leetcode #2 两数相加
题目
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807思路
分类讨论就行
代码
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null)return null;
ListNode head = new ListNode(0);
ListNode cur = head;
int tag = 0;
while(l1 != null || l2 != null){
int temp = 0;
if(l1 == null){
temp = l2.val + tag;
}
else if(l2 == null){
temp = l1.val + tag;
}
else{
temp = l1.val+l2.val+tag;
}
ListNode newNode = new ListNode(temp%10);
tag = temp/10;
cur.next = newNode;
cur = newNode;
if(l1!=null)l1 = l1.next;
if(l2!=null)l2 = l2.next;
}
if(tag != 0){
cur.next = new ListNode(1);
}
return head.next;
}
}
LeetCode 01两数之和&02两数相加
力扣
-
- LeetCode01两数之和
- LeetCode02两数之加
前言：第一次LeetCode打卡题解，前面组织的打卡活动从今天开始正式开始了，很多csdn和公众号小伙伴以及加入了，欢迎加入！详细看力扣打卡计划。关注笔者公众号：
bigsai回复进群即可进入。
LeetCode01两数之和
题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
分析：
题意就是让你从数组中找到两个位置他们对应位置的和为target。
本题主要有暴力和哈希两种方法：
法一：暴力法
把所有两两配对的问题全部遍历出来，直到找到满足题意的结果为止，时间复杂度O(n2)
代码：
/*
* 时间60ms
*/
public int[] twoSum(int[] nums, int target) {
int a[]=new int[2];
for(int i=0;i<nums.length;i++)
{
for(int j=i+1;j<nums.length;j++)
{
if(nums[i]+nums[j]==target)
{
a[0]=i;
a[1]=j;
return a;
}
}
}
return a;
}
法二：借助哈希(一次)
对于上述问题，你可能会疑问：能不能快速的直接知道这个数据是否存在呢？本题得目标是求得两个位置的和为target。这种问题当然可以使用哈希帮忙处理啊：
- 在第一次遍历你可以用一个HashMap先把各个位置的
值-位置当成Key-Value存储，然后进行第二次遍历只需要判断这个HashMap中是否存在(target-a[index])值就可以判断是否存在了。(这种情况要先遍历一遍，n个元素都要)
但是这种情况遇到两个相同的元素，只会储存一个Hash，就会被替代而出现错误！
能不能正确且再简单一点？
答案是可以的，其实我们不需要用hash存储所有，边走边存即可。为什么我们可以这么考虑？因为如果从数的特性来看： - 数是一对形式出现的
- 一对有前后位置之分，在遍历到前的时候不一定会找到后面的元素，但是遍历到后面的元素前面一定被我们存储了。
ac代码为：
/*
* 3ms
*/
public int[] twoSum2(int[] nums, int target) {
int a[]=new int[2];
Map<Integer, Integer>map=new HashMap<Integer, Integer>();
for(int i=0;i<nums.length;i++)
{
if(map.containsKey(target-nums[i]))
{
a[0]=i;
a[1]=map.get(target-nums[i]);
return a;
}
else {
map.put(nums[i], i);
}
}
return a;
}
LeetCode02两数之加
题目描述：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
分析：
本题其实就是用一个链表存储一个数字(逆序存储)，你需要给它计算出结果后在 逆序 存储到一个链表中返回。
所谓加法的运算规则：从两个数的最低位进行计算，进行到下一位的时候需要考虑进位问题。一直到最后，而本题所给的链表刚好可以用来直接计算，因为链表头都是数字最低位可以直接相加，然后一直遍历到结束。可以用一个常数表示进位。
在具体实现(链表)的时候：
- 创建新的链表，每次将计算的数值插入到链表尾部即可。
- 需要准确表示进位，并且最后要考虑以下进位
- 妥善返回正确节点，可以用一个头节点用来使得所有节点都正常操作，而不需要特殊判断。
通过代码第一次比较啰嗦的写法：
当然，如果你遍历链表把各个数字取出来，使用字符串、数字转换然后相加得到一个数字，最后在转成字符串、链表的理论可以，可以自行实现。
第一次比较臃肿但易理解代码为：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode node=new ListNode(0);//用一个头节点(不存真实的值)
ListNode team=node;
int jin=0;//进位
while(l1!=null&&l2!=null)//当可以正常相加时候
{
int num=l1.val+l2.val+jin;//该位理论的数字
jin=num/10;//进位0 或 1
num%=10;//实际能表示的数字
team.next=new ListNode(num);//将数字放到下一个节点中
team=team.next;//往下进行
l1=l1.next;l2=l2.next;
}
//其中一个为null或全为null时候
while (l1!=null) {
int num=l1.val+jin;
jin=num/10;
num%=10;
team.next=new ListNode(num);
team=team.next;
l1=l1.next;
}
while (l2!=null) {
int num=l2.val+jin;
jin=num/10;
num%=10;
team.next=new ListNode(num);
team=team.next;
l2=l2.next;
}
if(jin!=0)team.next=new ListNode(jin);
return node.next;
}
优化后的代码为：
//更简洁的写法
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode node=new ListNode(0);
ListNode team=node;
int jin=0;//进位
while(l1!=null||l2!=null)
{
int num=jin;
if(l1!=null)
{
num+=l1.val;l1=l1.next;
}
if(l2!=null)
{
num+=l2.val;l2=l2.next;
}
jin=num/10;
num%=10;
team.next=new ListNode(num);
team=team.next;
}
if(jin!=0)team.next=new ListNode(jin);
return node.next;
}
当然，如果遇到评论区或者其他好的方法也可以，如果我错误还请指正。
欢迎关注微信公众号：bigsai 回复进群即可加入一起刷题。目前已有一百多位战友。
本文分享 CSDN - Big sai。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
LeetCode 2. 两数相加
问题
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
思路
链表存储的顺序正好是按照「个十百千」的顺序，与计算加法相似，只要访问每个节点，求和进位即可
需要注意的是：
- 遍历的条件：因为题目没有说两个链表一样长，这也合理，比如13 + 1023，也要能够完成计算，所以条件应为两个链表有一个不为None，且不要忽略进位，如果进位存在的话，也要把进位值写到结果链表中；
- 输出的结果也是一个链表，最开始我还通过计算直接输出了一个整形...所以每一步的计算结果就直接写到链表中的节点中，且注意，返回的是链表的头；
代码如下：
class Solution:
"""
input: ListNode1, ListNode2
output: result ListNode
"""
def addTwoNumbers(self, l1, l2):
curr = ListNode(0)
head = curr
# 长度也可能不同
sumnext = sumcurr = 0
while None != l1 or None != l2 or sumnext != 0:
if None != l1:
sumnext += l1.val
l1 = l1.next
if None != l2:
sumnext += l2.val
l2 = l2.next
sumnext, sumcurr = divmod(sumnext, 10)
curr.next = ListNode(sumcurr)
curr = curr.next
return head.next
LeetCode 445. 两数相加 II
445. 两数相加 II
题目来源：https://leetcode-cn.com/problems/add-two-numbers-ii
题目
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7解题思路
思路：栈
在进阶提示中，要求不对输入链表进行修改，不能对链表中的节点进行翻转。
那么这里就可以考虑使用栈，利用栈先入后出的特性逆序处理链表。
在处理栈元素返回链表时，使用头插法处理，确保返回的链表顺序正确。
具体过程可以看下图：
代码实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# 入栈方法
def push_stack(node, stack):
while node:
stack.append(node.val)
node = node.next
# 定义栈
stack1 = []
stack2 = []
# 执行入栈操作
push_stack(l1, stack1)
push_stack(l2, stack2)
# 记录进位
carry = 0
# 哑节点，控制链表返回
dummy = ListNode(0)
# 进行计算
# 终止条件：当栈为空，或者进位为 0
while stack1 or stack2 or carry:
a, b = 0, 0
# 出栈计算
if stack1:
a = stack1.pop()
if stack2:
b = stack2.pop()
sum_ = a + b + carry
carry = sum_ // 10
mod = sum_ % 10
# 使用头插法
# 将结果放入返回链表中
# 这样返回的链表顺序才是正确的
node = ListNode(mod)
node.next = dummy.next
dummy.next = node
return dummy.next
实现结果
以上就是使用栈先入后出的特性，来逆序处理链表，进而解决《445. 两数相加 II》问题的主要内容。其中返回新链表时，使用头插法，确保返回的链表顺序正确。
欢迎关注微信公众号《书所集录》
关于LeetCode 剑指 Offer II 025. 链表中的两数相加和链表表示的两个数相加的介绍已经告一段落，感谢您的耐心阅读，如果想了解更多关于leetcode #2 两数相加、LeetCode 01两数之和&02两数相加、LeetCode 2. 两数相加、LeetCode 445. 两数相加 II的相关信息，请在本站寻找。
本文标签：
![[转帖]Ubuntu 安装 Wine方法（ubuntu如何安装wine）](https://www.gvkun.com/zb_users/cache/thumbs/4c83df0e2303284d68480d1b1378581d-180-120-1.jpg)
