题目描述

难度：简单

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

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

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]

解释：342 + 465 = 807

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内 0 <= Node.val <= 9 题目数据保证列表表示的数字不含前导零

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-two-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

我们不要被题目带偏了！！！ 这只是个简单的相加：

2,4,3
5,6,4
————————
7 0 8

我们只需要输出 7—>0—>8 链表即可，并不是输出 807 结果。

这是两个链表，那么我们可以进行同位置进行遍历即可，但是要注意进位，链表的遍历还需要注意保留一个指向链表头部的变量。

这题循环少不了。

解法：

public class Solution {
    /**
     * 自定义链表结构
     */
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 二话不说遍历链表
     * @param l1 第一个链表
     * @param l2 第二个链表
     * @return
     */
    static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
		//为了方便理解，用 one、two表示两个链表
        ListNode one = l1;
        ListNode two = l2;

        int count = 0;
        //构造一个新的链表，利用一个偏移量0作为头部
        ListNode head = new ListNode(0);
        ListNode cur = head;

        while (one != null || two != null) {
            int x = one != null ? one.val : 0;
            int y = two != null ? two.val : 0;
			
            //当前新位的值，需要考虑进位，第1个进位为0，但要考虑下一个进位，所以要+count
            int sum = x + y + count;
            //进位
            count = sum / 10;
		  //新的链表当前位的值
            cur.next = new ListNode(sum % 10);
            //链表下一位 next=next.next 套娃
            cur = cur.next;
		   //遍历的关键点	
            if (one != null) {
                one = one.next;
            }
            if (two != null) {
                two = two.next;
            }
        }
        //末位进1
        if (count > 0) {
            cur.next = new ListNode(1);
        }
		//去掉 首位的 0
        return head.next;
    }

    public static void main(String[] args) {
        //测试
        ListNode one = new ListNode(2);
        one.next = new ListNode(8);
        one.next.next = new ListNode(9);

        ListNode two = new ListNode(8);
        two.next = new ListNode(3);
        two.next.next = new ListNode(1);

//        2   8  9
//        8   3  1
//      —————————————————
//        0   2  1  1    
        ListNode returnNode2 = addTwoNumbers2(one, two);
        while (returnNode2 != null) {
            System.out.print(returnNode2.val + " ");
            returnNode2 = returnNode2.next;
        }
    }
}