• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

leetCode2. 两数相加

开发技术 开发技术 3小时前 1次浏览

leetCode2. 两数相加

1.题目描述

    给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
   请你将两个数相加,并以相同形式返回一个表示和的链表。
   你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

2.思路分析

1. 两条单链表存储两个数字,并且逆序排列,很符合我们的整数计算规则,及从最低位开始算,依次到最高位
2. 逆序排列的链表第一位刚好是整数的最低位,因此可以直接将两条链表的节点遍历取出来,将他们的值依次相加
3. 考虑进位问题,如果两个值相加 > 10 ,则有进位,定义carry变量保存进位值
4. 则 carry =  两数之和 (sum + carry) / 10
5. 两条链表求和,返回一个新链表,因此必须先定义一条新链表,用于保存链表的和
6. 每次向新链表中添加的值 value = (sum + carry(进位) ) % 10
7. 定义新链表,先定义头节点,因为头节点不能动,因此还需要一个辅助节点,类似一个指针,可以移动‘
8. 遍历完两个链表结束后还有判断carry是否有进位,有进位还要再新增一个节点,保存进位

3.源码及分析

//节点
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;
        }
    }
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        //定义一个头节点和尾节点
        //tail节点类似一个辅助指针,因为链表在定义后头节点head不能动(一旦动之后链表将会断开)
        ListNode head = null, tail = null;
        //设置进位位
        int carry = 0;
        //循环遍历两个单链表,依次将两个链表的值相加
        //当且仅当两个链表的都为空时,结束遍历
        while (l1 != null || l2 != null) {

            //记录当前次遍历时 链表是否位空,若不为空,则记录值,若为空,则保存0
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;

            //定义sum保存当前次遍历两个链表的总和(后续会通过取模和除法拿到进位值和要保存到值)
            int sum = n1 + n2 + carry;

            //判断链表是否为空,向链表添加节点
            if (head == null) {
                //遍历第一次时向链表添加第一个节点,值为 sum % 10
                head = tail = new ListNode(sum % 10);
            } else {
                //第一次以后的遍历依次向链表添加节点
                tail.next = new ListNode(sum % 10);
                //指针后移
                tail = tail.next;
            }
            
            //根据当前两个数相加的结果除以10 重置进位位
            carry = sum / 10;

            //原链表指针后移进行下一次循环(先判断是否为空)
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        //循环结束后(即最后一次两个链表的节点值相加之后如果还有进位),向链表再增加一个节点,即进位节点
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        //返回节点
        return head;
}

程序员灯塔
转载请注明原文链接:leetCode2. 两数相加
喜欢 (0)