【LeetCode：02 两数相加】

简介

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

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

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

解题思路

这题我当时写的时候 就是单纯的模拟，只不过通常模拟题需要考虑的细节会比较多，这里主要注意的是

1.把两个链表变为等长 方便直接相加

2.如果相加超9 要进位

3.进位的结果如果最后超过的 链表的长度 需要再增加一个节点

4.结果记录在 第一个链表中

算法实现

class Solution 
{
    public ListNode     addTwoNumbers(ListNode l1, ListNode l2) {
        int x1=0,x2=0;
        ListNode t1=new ListNode();
        ListNode t2=new ListNode();
        ListNode t=new ListNode();//用作头插法 由于后续链表扩容
        t1=l1;// 这里的主要作用是记录 原链表的头结点
        t2=l2;
        while(l1.next!=null||l2.next!=null)// 把l1链表与l2链表扩容到一样长
        {// 若谁短 谁扩容
            if(l1.next==null)// 链表 头插法
            {
                ListNode l= new ListNode(0);
                t=l1;
                t.next=l;
                l=t;
            }
            if(l2.next==null)// 链表头插法
            {
                ListNode l= new ListNode(0);
                t=l2;
                t.next=l;
                l=t;
            }
            l1=l1.next;
            l2=l2.next;
        }
        ListNode res = new ListNode();// 结果链表
        res=t1;// 结果用res存 res记录的是t1链表的头结点 因为t1 t2不断向后加 所有t1不能用作结果遍历
        int flag=0;// 如果最后节点相加大于9 进位扩容 然后标记退出，这里flag就是用于标记退出
        while(t1!=null)
        {
            int cnt=t1.val+t2.val;// 对应节点相加
            if(cnt>9)// 如果结果大于10
            {
                cnt-=10;// 进位
                if(t1.next==null)// 最后节点相加值也进位了
                {
                    ListNode l= new ListNode(0);// 扩容
                    t=t1;
                    t.next=l;
                    l=t;
                    flag=1;// 标记退出
                }
                t1.next.val+=1;// 进位数存在t1的下一个节点
            }
            t1.val=cnt;// 如果没有进位 就直接存值 如果进位就存值-10
            t1=t1.next;// 下一个节点
            t2=t2.next;// 下一个节点
            if(flag==1)// 如果如果最后节点相加大于9 进位扩容 然后标记退出
                break;// 退出
        }
        return res;// 结果
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：41.3 MB, 在所有 Java 提交中击败了36.93%的用户

可以看出速度还是可以的，但因为做法比较暴力，直接就把链表扩容 所以内存消耗并不优秀。