leetCode2. 两数相加

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. 两数相加

原文：https://www.cnblogs.com/mx-info/p/14729006.html