2_两数相加
【问题描述】
给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]
解:
【算法设计思想】
注意理清题意,结合链表通常在尾部进行数据修改的特点,所以才会有题目中的“每位数字都是按照逆序的方式存储的”。在这里,要考虑到进位问题,大体的思路就是先分配一个空链表,设立头、尾两个指针,利用carry变量来记录进位的数字,模拟手算过程。在遍历过程结束以后,即计算到最高位时,要注意是否会进位。例如,566+468=1034,这里应该再分配一个内存空间来存储多余的那个“1”。
【算法描述】
C语言:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode *head = NULL, *tail = NULL;
int carry = 0;
while (l1 || l2) {
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = n1 + n2 + carry;
if (!head) {
head = tail = malloc(sizeof(struct ListNode));
tail->val = sum % 10;
tail->next = NULL;
} else {
tail->next = malloc(sizeof(struct ListNode));
tail->next->val = sum % 10;
tail = tail->next;
tail->next = NULL;
}
carry = sum / 10;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
}
if (carry > 0) {
tail->next = malloc(sizeof(struct ListNode));
tail->next->val = carry;
tail->next->next = NULL;
}
return head;
}
Java:
/**
* 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 head = null;
ListNode tail = null;
int carry = 0;
while(l1 != null || l2 != null){
int n1 = (l1 != null)? l1.val : 0;
int n2 = (l2 != null)? l2.val : 0;
int sum = n1 + n2 + carry;
if(head == null){
head = tail = new ListNode(sum % 10);
}else{
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if(l1 != null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
}
if(carry > 0){
tail.next = new ListNode(carry);
tail = tail.next;
}
return head;
}
}
Python:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
head = None
tail = None
carry = 0
while l1 != None or l2 != None:
n1 = l1.val if (l1 != None) else 0
n2 = l2.val if (l2 != None) else 0
sum = n1 + n2 + carry
if head == None:
head = tail = ListNode(sum % 10)
else:
tail.next = ListNode(sum % 10)
tail = tail.next
carry = sum // 10
if l1 != None:
l1 = l1.next
if l2 != None:
l2 = l2.next
if carry > 0:
tail.next = ListNode(carry)
tail = tail.next
return head
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 = nullptr;
ListNode* tail = nullptr;
int carry = 0;
while (l1 != nullptr || l2 != nullptr) {
int n1 = (l1 != nullptr) ? l1->val : 0;
int n2 = (l2 != nullptr) ? l2->val : 0;
int sum = n1 + n2 + carry;
if (head == nullptr) {
head = tail = new ListNode(sum % 10);
} else {
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10;
if (l1 != nullptr) {
l1 = l1->next;
}
if (l2 != nullptr) {
l2 = l2->next;
}
}
if (carry > 0) {
tail->next = new ListNode(carry);
tail = tail->next;
}
return head;
}
};
标签:ListNode,val,相加,next,tail,l2,l1,两数
From: https://www.cnblogs.com/zeta186012/p/18350815