链表按位求和

描述

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。在下次两个节点数据相加的时候，将临时数据也相加进去。

代码具体实现

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