本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目描述

2. 两数相加

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

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

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

二、思路分析

首先两个链表长度不一。按照常规计算我们就从链表头部开始进行加操作。这个会有三个变量参与计算

start、 end都很好理解就是两个链表中对应的值，up我们理解为寄存器因为我们两数相加会产生进位。

因为链表是可以不断追加的，我们不需要考虑越界的问题。

三、AC 代码

入口方法

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    List<Integer> list1 = getTotalFromListNode(l1);
    List<Integer> list2 = getTotalFromListNode(l2);
    List<Integer> totalList = addListInteger(list1,list2);
    ListNode node = getListNodeFromTotal(totalList);
    return node;
}
复制代码

模拟加法

/**
 * 两个list相加 ， 模拟加法
 * @param list1
 * @param list2
 * @return
 */
private List<Integer> addListInteger(List<Integer> list1, List<Integer> list2) {
    List<Integer> list = new ArrayList<>();
    Integer length = list1.size() > list2.size() ? list1.size() : list2.size();
    //进位管理器
    Integer up = 0;
    Integer start = 0;
    Integer end = 0;
    for (Integer i = 0; i < length; i++) {
        if (i < list1.size()) {
            start = list1.get(i);
        }
        if (i < list2.size()) {
            end = list2.get(i);
        }
        int total = start + end + up;
        //total个位存入新的list , 十位存入进位管理器
        up = total / 10;
        list.add(total % 10);
        //清空
        start = 0;
        end = 0;
    }
    //最后判断进位管理器是否有进位数据
    if (up != 0) {
        list.add(up);
    }
    return list;
}

private ListNode getListNodeFromTotal(List<Integer> totalList) {
    ListNode node = new ListNode(0);
    ListNode temNode = node;
    for (int i = 0; i < totalList.size(); i++) {
        ListNode subNode = new ListNode(totalList.get(i));
        temNode.next = subNode;
        temNode = subNode;
    }
    return node.next;
}

private List<Integer>  getTotalFromListNode(ListNode node) {
    List<Integer> list = new ArrayList<>();
    while (node != null) {
        list.add(node.val);
        node = node.next;
    }
    return list;
}
复制代码