LeetCode-problem2

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

链表

public class Solution1 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode list = new ListNode(0);                      //设置哑节点来存储头指针的位置，防止最后链表为空的情况
        ListNode t1 = l1;
        ListNode t2 = l2;
        ListNode temp = list;
        int carry = 0;                                        //表示相加过程中的进位

        while (t1 != null || t2 != null) {
                                                              //较短的一侧链表使用0来进行补全
            int x = (t1 == null) ? 0 : t1.val;
            int y = (t2 == null) ? 0 : t2.val;
            int sum = x + y + carry;
            carry = sum / 10;
            temp.next = new ListNode(sum % 10);                //产生新的节点，将本位和存入该节点
            temp = temp.next;
                                                               //两个链表同时进行需要对两者进行判空处理
            if (t1 != null) {
                t1 = t1.next;
            }
            if (t2 != null) {
                t2 = t2.next;
            }
        }

        if (carry > 0) {
            temp.next = new ListNode(carry);                    //将最后的进位加入链表中
        }

        return list.next;
    }


/* Definition for singly-linked list. */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

复杂度分析：

• 时间复杂度：O(max⁡(m,n))
• 空间复杂度：O(max⁡(m,n))

考虑进位的问题，保留头指针作为最后的返回值，设置哑节点防止最后链表出现空的情况