LeetCode(力扣Java算法刷题)两数相加

2023-12-13 10:03:21

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

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

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

思路
标签:链表
将两个链表看成是相同长度的进行遍历,如果一个链表较短则在前面补 000
每一位计算的同时需要考虑上一位的进位问题,而当前位计算结束后同样需要更新进位值
如果两个链表全部遍历完毕后,进位值为 111,则在新链表最前方添加节点 111
小技巧:对于链表问题,返回结果为头结点时,通常需要先初始化一个预先指针 pre,该指针的下一个节点指向真正的头结点 head。使用预先指针的目的在于链表初始化时无可用节点值,而且链表构造过程需要指针移动,进而会导致头指针丢失,无法返回结果。

/**
 * 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 prev = new ListNode(0);
        //定义一个进位数的指针,用来存储当两数之和大于10的时候,
        int carry = 0;
        //定义一个可移动的指针,用来指向存储两个数之和的位置
        ListNode cur = prev;
        //当l1 不等于null或l2 不等于空时,就进入循环
        while(l1!=null || l2!=null){
            //如果l1 不等于null时,就取他的值,等于null时,就赋值0,保持两个链表具有相同的位数
            int x= l1 !=null ? l1.val : 0;
             //如果l1 不等于null时,就取他的值,等于null时,就赋值0,保持两个链表具有相同的位数
            int y = l2 !=null ? l2.val : 0;
            //将两个链表的值,进行相加,并加上进位数
            int sum = x + y + carry;
            //计算进位数
            carry = sum / 10;
            //计算两个数的和,此时排除超过10的请况(大于10,取余数)
            sum = sum % 10;
            //将求和数赋值给新链表的节点,
            //注意这个时候不能直接将sum赋值给cur.next = sum。这时候会报,类型不匹配。
            //所以这个时候要创一个新的节点,将值赋予节点
            cur.next = new ListNode(sum);
            //将新链表的节点后移
            cur = cur.next;
            //当链表l1不等于null的时候,将l1 的节点后移
            if(l1 !=null){
                l1 = l1.next;
            }
            //当链表l2 不等于null的时候,将l2的节点后移
            if(l2 !=null){
                l2 = l2.next;
            } 
        }
        //如果最后两个数,相加的时候有进位数的时候,就将进位数,赋予链表的新节点。
        //两数相加最多小于20,所以的的值最大只能时1
        if(carry == 1){
            cur.next = new ListNode(carry);
        }
        //返回链表的头节点
        return prev.next;
    }
}

文章来源:https://blog.csdn.net/qq_73735007/article/details/134444445
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。