两数相加||

题目描述：

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。

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

示例：

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

题解

思路：
由数字存储顺序得，无法直接相加两个单链表的值。为了可以直接相加两链表，所以反转两个链表。（分别求出链表代表的数字，再相加会超出int的范围）然后，用链表的头插法（逆序创建，负负得正）创建一个新的链表，并返回头结点。

class Solution {
    // 反转单链表需要先存储链表结点
    public ListNode reverse(ListNode n)
    {
        ListNode[] node = new ListNode[100];
        int i = 0;
        while (n != null)
        {
            node[i++] = n;
            n = n.next;
        }
        i--;
        int j = i;
        while (i != 0)
        {
            node[i].next = node[i-1];
            i--;
        }
        node[0].next = null;
        return node[j];
    }
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        
        ListNode head = null, tail = null;
        // 解决进位问题，结果大于等于10时，剩余值到下一个循环
        int n = 0;   
        while (l1 != null || l2 != null || n != 0)
        {
            if (l1 != null)
                n += l1.val;
            if (l2 != null)
                n += l2.val;

            tail = new ListNode(n%10);
            n /= 10;
                
            tail.next = head;
            head = tail;
            
             
            if (l1 != null)
                l1 = l1.next;
            
            if (l2 != null)
                l2 = l2.next;
        }
        return head;
    }
}