目錄
一、兩數(shù)相加
1、題目
2、題目解讀
3、代碼
二、反轉(zhuǎn)鏈表
1、題目
?2、題目解讀
3、代碼?
三、兩數(shù)相加 II
1、題目
2、題目解讀
3、代碼
反轉(zhuǎn)鏈表再進行計算
借助棧
一、兩數(shù)相加
1、題目
2. 兩數(shù)相加 - 力扣（Leetcode）
給你兩個?非空?的鏈表，表示兩個非負的整數(shù)。它們每位數(shù)字都是按照?逆序?的方式存儲的，并且每個節(jié)點只能存儲?一位?數(shù)字。
請你將兩個數(shù)相加，并以相同形式返回一個表示和的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 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]
提示：
- 每個鏈表中的節(jié)點數(shù)在范圍?
[1, 100]?內(nèi) 0 <= Node.val <= 9- 題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零
2、題目解讀
因為題目所給鏈表節(jié)點的范圍是[1,100],所以我們無法通過將兩個鏈表轉(zhuǎn)換成兩個數(shù)再進行計算，然后重新轉(zhuǎn)換成鏈表，數(shù)太大了。
題目說：它們每位數(shù)字都是按照?逆序?的方式存儲的，并且每個節(jié)點只能存儲?一位?數(shù)字。
因此我們就直接進行計算兩個鏈表的值，然后對10進行取模，再進行進位操作。
如下操作：
sum = x + y + carry
carry = sum / 10
sum = sum % 10還需要注意的是如果最后sum不為0還需要進位，也就是再添加一個節(jié)點。
運行條件：鏈表從頭遍歷到尾，逐位相加 （1）需要保存進位 （2）需要保存結(jié)果
結(jié)束時：
- 兩個鏈表只要有一個非空就需要往后進行
- 如果鏈表遍歷結(jié)束，進位不為0，需要把進位項添加在鏈表后面
3、代碼
java：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while(l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
if(carry == 1) {
cur.next = new ListNode(carry);
}
return pre.next;
}
}
Python
# 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:
# 創(chuàng)建一個結(jié)點值為 None 的頭結(jié)點, dummy 和 p 指向頭結(jié)點, dummy 用來最后返回, p 用來遍歷
dummy = p = ListNode(None)
s = 0 # 初始化進位 s 為 0
while l1 or l2 or s:
# 如果 l1 或 l2 存在, 則取l1的值 + l2的值 + s(s初始為0, 如果下面有進位1, 下次加上)
s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
p.next = ListNode(s % 10) # p.next 指向新鏈表, 用來創(chuàng)建一個新的鏈表
p = p.next # p 向后遍歷
s //= 10 # 有進位情況則取模, eg. s = 18, 18 // 10 = 1
l1 = l1.next if l1 else None # 如果l1存在, 則向后遍歷, 否則為 None
l2 = l2.next if l2 else None # 如果l2存在, 則向后遍歷, 否則為 None
return dummy.next # 返回 dummy 的下一個節(jié)點, 因為 dummy 指向的是空的頭結(jié)點, 下一個節(jié)點才是新建鏈表的后序節(jié)點
二、反轉(zhuǎn)鏈表
1、題目
206. 反轉(zhuǎn)鏈表 - 力扣（Leetcode）
給你單鏈表的頭節(jié)點?head?，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
示例 1：
輸入：head = [1,2,3,4,5] 輸出：[5,4,3,2,1]
示例 2：
輸入：head = [1,2] 輸出：[2,1]
示例 3：
輸入：head = [] 輸出：[]
提示：
- 鏈表中節(jié)點的數(shù)目范圍是?
[0, 5000] -5000 <= Node.val <= 5000
?2、題目解讀
鏈表簡單反轉(zhuǎn)
3、代碼?
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode cur=head;
while (cur!=null){
ListNode tmp=cur.next;
cur.next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
}Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur:
temp = cur.next # 先把原來cur.next位置存起來
cur.next = pre
pre = cur
cur = temp
return pre
三、兩數(shù)相加 II
1、題目
給你兩個?非空?鏈表來代表兩個非負整數(shù)。數(shù)字最高位位于鏈表開始位置。它們的每個節(jié)點只存儲一位數(shù)字。將這兩數(shù)相加會返回一個新的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)字都不會以零開頭。
示例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- 輸入數(shù)據(jù)保證鏈表代表的數(shù)字無前導(dǎo) 0
2、題目解讀
這題拆解開來就是上面兩題，先進行鏈表反轉(zhuǎn)，然后繼續(xù)兩數(shù)相加。
或者通過棧來完成鏈表上面數(shù)的保存，然后進行計算。
3、代碼
反轉(zhuǎn)鏈表再進行計算
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre1=null;
ListNode cur1=l1;
while (cur1!=null){
ListNode tmp=cur1.next;
cur1.next=pre1;
pre1=cur1;
cur1=tmp;
}
ListNode pre2=null;
ListNode cur2=l2;
while (cur2!=null){
ListNode tmp=cur2.next;
cur2.next=pre2;
pre2=cur2;
cur2=tmp;
}
l1=pre1;
l2=pre2;
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while(l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
if(carry == 1) {
cur.next = new ListNode(carry);
}
cur=pre.next;
pre=null;
while (cur!=null){
ListNode tmp=cur.next;
cur.next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
}借助棧
使用棧區(qū)進行存儲數(shù)字，然后再相加計算。文章來源：http://www.zghlxwxcb.cn/news/detail-528280.html
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode head = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
int sum = carry;
sum += stack1.isEmpty()? 0: stack1.pop();
sum += stack2.isEmpty()? 0: stack2.pop();
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
carry = sum / 10;
}
return head;
}
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-528280.html
到了這里，關(guān)于LeetCode——兩數(shù)相加的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
