两数相加

image.png

注意：两个链表长度不一定相同

思路:暴力破解法可以将链表中数字循环取出并且转为整数，然后相加，然后再转为链表。但是不确定链表长度的情况下有可能超出数据类型的最大限制。根据链表的每个节点只存放个位数，所以采用了链表中每个对应位置相加，进位用变量表示的方法。
数据结构：链表
算法思维：遍历、取模、累加

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode p = l1, q = l2;
            ListNode head = new ListNode(-1);
            ListNode cur = head;
            //进位
            int carry = 0;
            //遍历两个链表
            while (p != null || q != null) {
                //获取当前节点的值：链表较短，已无节点，取0
                int x = (p != null) ? p.val : 0;
                int y = (q != null) ? q.val : 0;
                //对应位置的节点数值相加
                int sum = x + y + carry;
                carry = sum / 10;
                int num = sum % 10;
                //将计算结果插入链表尾部
                cur.next = new ListNode(num);
                cur = cur.next;

                p = p == null ? p : p.next;
                q = q == null ? q : q.next;
            }

            if (carry > 0) { //处理进位节点
                cur.next = new ListNode(carry);
            }

            return head.next;
        }