两数相加

àì夳堔傛蜴生んèń 2022-12-03 12:49 135阅读 0赞

# 两数相加 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/add-two-numbers/

## 2、题目要求 ##

> **题目描述**

给出两个 **非空** 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 **逆序** 的方式存储的，并且它们的每个节点只能存储 **一位** 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

> **示例：**

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

## 3、代码思路 ##

低位相加，有可能需要向高位进 `1`，所以我们添加 `carry` 变量，用于记录上次相加的结果是否需要向高位进位，`carry = 0` 表示不需要向高位进位，`carry = 1` 表示需要向高位进位

## 4、代码实现 ##

代码

/**
     * @ClassName DddTwoNumbersDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/9/3 12:47
     * @Version 1.0
     */
    public class DddTwoNumbersDemo {
        
    
        public static void main(String[] args) {
        
    
            ListNode list1 = new ListNode(2);
            list1.next = new ListNode(4);
            list1.next.next = new ListNode(3);
    
            ListNode list2 = new ListNode(5);
            list2.next = new ListNode(6);
            list2.next.next = new ListNode(4);
    
            Solution solution = new Solution();
            ListNode sumList = solution.addTwoNumbers(list1, list2);
    
        }
    
    }
    
    class Solution {
        
        /**
         * 两数相加
         * @param list1 链表 1
         * @param list2 链表 2
         * @return 相加后的链表
         */
        public ListNode addTwoNumbers(ListNode list1, ListNode list2) {
        
            ListNode list1Pointer = list1;
            ListNode list2Pointer = list2;
            ListNode dummyHead = new ListNode(0);
            ListNode sumListPointer = dummyHead;
            int carry = 0; // 进位标志位，为 0 表示不进位，为 1 表示进位
            int sum = 0; // 当前位的加和
    
            while (list1Pointer != null || list2Pointer != null || carry != 0) {
        
                // list1Pointer 指针不为空
                if (list1Pointer != null) {
        
                    sum += list1Pointer.val; // 累加
                    list1Pointer = list1Pointer.next; // 指针后移
                }
    
                // list2Pointer 指针不为空
                if (list2Pointer != null) {
        
                    sum += list2Pointer.val; // 累加
                    list2Pointer = list2Pointer.next; // 指针后移
                }
                sum += carry; // 加上进位标志位
                carry = sum / 10; // 获取本次的进位标志位（十位数）
                sum = sum % 10; // 获取当前位的值（个位数）
                sumListPointer.next = new ListNode(sum); // 创建新节点
                sumListPointer = sumListPointer.next; // 指针后移
                sum = 0; // 加和清零
            }
    
            return dummyHead.next;
        }
    }
    
    class ListNode {
        
        int val;
        ListNode next;
    
        ListNode(int x) {
        
            val = x;
        }
    }