[Java·算法·中等]LeetCode2. 两数相加-两个链表值相加生成新链表

怼烎@ 2023-09-24 20:27 40阅读 0赞

#### 每天一题，防止痴呆 ####

*  题目
 *  示例
 *  分析思路1
 *  题解1

## 题目 ##

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

## 示例 ##

输入：l1 = [2,4,3], l2 = [5,6,4]
    输出：[7,0,8]
    解释：342 + 465 = 807.

输入：l1 = [0], l2 = [0]
    输出：[0]

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    输出：[8,9,9,9,0,0,0,1]

## 分析思路1 ##

定义一个新的链表来存储结果，同时定义一个变量 carry 来表示进位。

遍历两个链表，对于每一位，将两个链表的对应节点值相加，再加上进位 carry 的值。

如果相加的结果大于等于 10，那么需要将进位 carry 设置为 1，否则设置为 0。

将相加的结果对 10 取模，将得到的余数作为新链表的节点值，同时将进位 carry 传递给下一位的运算。

如果两个链表中有一个链表遍历结束，那么需要将另一个链表剩余的节点值与进位 carry 相加，并将结果添加到新链表中。

最后如果进位 carry 的值为 1，需要在新链表最后添加一个值为 1 的节点。

## 题解1 ##

/**
     * 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 result = new ListNode(0);
            ListNode temp = result ;
            int carry = 0;
            while (l1!=null || l2!=null){
        
                int x = l1!=null ? l1.val : 0;
                int y = l2!=null ? l2.val : 0;
                int sum = x + y + carry;
                carry = sum>=10 ? 1 : 0;
                temp.next = new ListNode(sum%10);
                temp = temp.next;
                if(l1!=null){
        l1=l1.next;}
                if(l2!=null){
        l2=l2.next;}
            }
            if(carry>0){
        
                temp.next = new ListNode(carry);
            }
            return result.next;
        }
    }

执行结果  
![在这里插入图片描述][fcd319ed8b494bd89423215c6755f743.png]

[fcd319ed8b494bd89423215c6755f743.png]: https://img-blog.csdnimg.cn/fcd319ed8b494bd89423215c6755f743.png