赞
赏
leetcode 官方第 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
求两个链表的数值之和,其实和我们的人类的思维差不多,我们可以一个节点一个节点的遍历,然后相加,我们需要一个临时的数据用来将前一步操作的值保存下来,用来判断当前两个节点相加的时候是否需要多加一个值。
我们可以同时对链表进行遍历,将相同位置的值取出来,然后进行相加。这边需要考虑到的情况是,如果两个数值相加大于 10,我们该怎么处理。计算当前节点数据的时候,是否需要加 1。需要将上次计算是否大于 10 的情况记录下来。
我们再分析一个负责的场景。
在计算 18 取 8 的时候,我们需要用到取余方法。在整体过程中我们需要定义一个中间变量,用来存储,它的上次计算结果是否大于10。如果大于 10,我们将中间结果记为 1。如果小于 10。我们记录为 0。在下次两个节点数据相加的时候,将临时数据也相加进去。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* l1CurrentNode = l1;
struct ListNode* l2CurrentNode = l2;
struct ListNode* retNode = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* retCurrentNode = retNode;
//用来临时记录,下次计算两个节点值的时候是否需要多加 1
int tmpValue = 0;
//遍历两个链表节点
while(l1CurrentNode != NULL || l2CurrentNode != NULL){
int l1CurrentValue = 0;
int l2CurrentValue = 0;
if(l1CurrentNode != NULL){
l1CurrentValue = l1CurrentNode->val;
l1CurrentNode = l1CurrentNode->next;
}
if(l2CurrentNode != NULL){
l2CurrentValue = l2CurrentNode->val;
l2CurrentNode = l2CurrentNode->next;
}
//计算相应的节点和
int currentValue = l1CurrentValue + l2CurrentValue + tmpValue;
if(currentValue >= 10){
tmpValue = 1;
currentValue = currentValue%10;
}else{
tmpValue = 0;
}
struct ListNode* tmpNode = (struct ListNode*)malloc(sizeof(struct ListNode));
tmpNode->val = currentValue;
tmpNode->next = NULL;
retCurrentNode->next = tmpNode;
retCurrentNode = retCurrentNode->next;
}
//如果最后两个值相加值比 10 大,那么需要将 1 添加到最后节点
if(tmpValue > 0){
struct ListNode* tmpNode = (struct ListNode*)malloc(sizeof(struct ListNode));
tmpNode->val = 1;
tmpNode->next = NULL;
retCurrentNode->next = tmpNode;
}
return retNode->next;
}
/**
* 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 l1CurrentNode = l1;
ListNode l2CurrentNode = l2;
ListNode retNode = new ListNode();
ListNode retCurrentNode = retNode;
//用来临时记录,下次计算两个节点值的时候是否需要多加 1
int tmpValue = 0;
//遍历两个链表节点
while(l1CurrentNode != null || l2CurrentNode != null){
int l1CurrentValue = 0;
int l2CurrentValue = 0;
if(l1CurrentNode != null){
l1CurrentValue = l1CurrentNode.val;
l1CurrentNode = l1CurrentNode.next;
}
if(l2CurrentNode != null){
l2CurrentValue = l2CurrentNode.val;
l2CurrentNode = l2CurrentNode.next;
}
//计算相应的节点和
int currentValue = l1CurrentValue + l2CurrentValue + tmpValue;
if(currentValue >= 10){
tmpValue = 1;
currentValue = currentValue%10;
}else{
tmpValue = 0;
}
retCurrentNode.next = new ListNode(currentValue);
retCurrentNode = retCurrentNode.next;
}
//如果最后两个值相加值比 10 大,那么需要将 1 添加到最后节点
if(tmpValue > 0){
retCurrentNode.next = new ListNode(1);
}
return retNode.next;
}
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var(
l1CurrentNode *ListNode = l1
l2CurrentNode *ListNode = l2
retNode *ListNode = new(ListNode)
//用来临时记录,下次计算两个节点值的时候是否需要多加 1
tmpValue = 0
retCurrentNode = retNode
)
//遍历两个链表节点
for {
if l1CurrentNode == nil && l2CurrentNode == nil {
break
}
var l1CurrentValue = 0
var l2CurrentValue = 0
if l1CurrentNode != nil {
l1CurrentValue = l1CurrentNode.Val
l1CurrentNode = l1CurrentNode.Next
}
if l2CurrentNode != nil {
l2CurrentValue = l2CurrentNode.Val
l2CurrentNode = l2CurrentNode.Next
}
//计算相应的节点和
var currentValue = l1CurrentValue + l2CurrentValue + tmpValue
if currentValue >= 10 {
tmpValue = 1
currentValue = currentValue%10
}else{
tmpValue = 0
}
var nextListNode *ListNode = new(ListNode)
nextListNode.Val = currentValue
retCurrentNode.Next = nextListNode
retCurrentNode = retCurrentNode.Next
}
//如果最后两个值相加值比 10 大,那么需要将 1 添加到最后节点
if tmpValue > 0 {
var tmpListNode *ListNode = new(ListNode)
tmpListNode.Val = 1
retCurrentNode.Next = tmpListNode
}
return retNode.Next;
}