嗨客网搜索
链表按位求和

描述

leetcode 官方第 2 题。给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

06_链表按位求和.png

输入: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
  • 题目数据保证列表表示的数字不含前导零

思路

求两个链表的数值之和,其实和我们的人类的思维差不多,我们可以一个节点一个节点的遍历,然后相加,我们需要一个临时的数据用来将前一步操作的值保存下来,用来判断当前两个节点相加的时候是否需要多加一个值。

07_链表按位求和.png

我们可以同时对链表进行遍历,将相同位置的值取出来,然后进行相加。这边需要考虑到的情况是,如果两个数值相加大于 10,我们该怎么处理。计算当前节点数据的时候,是否需要加 1。需要将上次计算是否大于 10 的情况记录下来。

我们再分析一个负责的场景。

08_链表按位求和.png

在计算 18 取 8 的时候,我们需要用到取余方法。在整体过程中我们需要定义一个中间变量,用来存储,它的上次计算结果是否大于10。如果大于 10,我们将中间结果记为 1。如果小于 10。我们记录为 0。在下次两个节点数据相加的时候,将临时数据也相加进去。

代码具体实现

C语言版本

/** * 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; }

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 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; } }

Go语言版本

/** * 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; }

赞助商链接:


嗨客网顶部