一分钟解决数据结构问题---两个链表数值相加（简单易理解）

一分钟解决数据结构问题---两个链表数值相加（简单易理解）

此题为力扣中等链表题目

 文章目录：

1️⃣.题目解析

2️⃣.代码实现

3️⃣.全部代码

题目：

---

1️⃣.题目解析

①.题目给定的是两个非空的链表表示两个非负的整数

❗️ 注意这里给定的是非空，所以这里不需要判断 l1 和 l2 链表是不是非空

②.每位数字都是逆序进行存储的

❗️ 就是说链表的头结点是整数的最低数值位（个位），从头结点到尾结点数值位依次增大

例：下图这样一个链表

③.每个结点只能存储一位数值

❗️ 即每个结点的数值域范围是： 0 ~ 9 左右都是闭区间

④.两个链表都是不会以 0 开头

❗️ 所以链表结点个数就是该数值的位数

⑤.最后要求返回新链表的头

---

2️⃣.代码实现

步骤一、定义一个头结点，该头结点为新链表的头结点，程序结束用于返回

ListNode head = null;

步骤二、定义一个 cur 用于遍历链表，起到连接链表的作用

ListNode cur = head;

步骤三、定义一个结点 node 用于存储加和出来的新链表的结点

ListNode node = null;

步骤四、当两个数值总和大于 10，就存在进位的问题，当两个数值加和大于 0 该位应该是总和取余 10 的结果，然后下一位（高位）进 1

例如题目中的加和例子：

图解：

int carrybit = 0;

步骤五、定义一个 sum 用于记录两个链表的数值加和

int sum = 0;

步骤六、循环去加和两个链表的数值，循环的终止条件是两个链表都为空了，即所有的数值都进行加和完毕

while(l1 != null || l2 != null)

步骤七、判断两个链表有没有走到空，如果哪个链表先走到空，那么向后的数值都是 0 ，这里使用到了三目运算符，先判断为不为空，不为空是链表的数值，为空数值为 0 ，这样做是为了防止空指针异常

int num1 = l1 != null ? l1.val : 0;
int num2 = l2 != null ? l2.val : 0;

步骤七、求出加和后的数值，并利用这个数值创建一个新的结点

sum = num1 + num2 + carrybit;
node = new ListNode(sum%10);

步骤八、判断 sum 数值是不是大于 10，大于 10 存在进位的问题，这里把 carrybit 赋值为 sum / 10,
由于两个链表的数值都是 0 ~ 9，所以 sum 范围：0 ~ 18，所以 sum / 10 后就可以算出来的结果无非是 0 / 1，这样就可以知道需不需要进位，0 不进位，1 进位

carrybit = sum / 10;

步骤九、使用尾插法进行链表结点插入，先得到的是链表数值和的个位，这样依次进行尾插存储，正好满足题目的逆序要求

if (head == null){
                head = node;
                cur = node;
            }
            else{
                cur.next = node;
                cur = cur.next;
            }

步骤十、判断如果两个链表为不为空，不为空结点向后移动，继续进行数值的加和

if (l1 != null){
                l1 = l1.next;
            }
            if (l2 != null){
                l2 = l2.next;
            }

步骤十一、如果最后 carrybit 还是大于 0 的证明还需要向高位进 1 ，就再新创建一个结点，尾插到链表中，这种情况的最高位是 0 ，所以直接使用 1 去新建结点即可

if (carrybit > 0){
            node = new ListNode(carrybit);
            cur.next = node;
        }

步骤十二、返回新链表的头结点

return head;

---

3️⃣.全部代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //用来记录进位
        int carrybit = 0;
        ListNode head = null;
        ListNode cur = head;
        ListNode node = null;
        int sum = 0;
        while(l1 != null || l2 != null){
            int num1 = l1 != null ? l1.val : 0;
            int num2 = l2 != null ? l2.val : 0;
            sum = num1 + num2 + carrybit;
            node = new ListNode(sum%10);
            carrybit = sum / 10;
            if (head == null){
                head = node;
                cur = node;
            }
            else{
                cur.next = node;
                cur = cur.next;
            }
            if (l1 != null){
                l1 = l1.next;
            }
            if (l2 != null){
                l2 = l2.next;
            }
        }
        if (carrybit > 0){
            node = new ListNode(carrybit);
            cur.next = node;
        }
        return head;
    }
}