LeetCode2之两数相加(Add Two Numbers)-蒲公英云

LeetCode2之两数相加(Add Two Numbers)

一、题目

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyZWVfaWZjb25maWc_size_16_color_FFFFFF_t_70

二、一种解题思路

1）介绍：暴力解法（感觉没别的了吧，可能是我笨吧，原地爆炸下）

 方法思路：一路遍历，一路加，遇到一个链表的next为null时，则停止遍历该链表，并且让另一个链表的剩余节点和0相加。若链表已经遍历完了，还存在进位数，则在创建一个next节点。

时间复杂度：O(Max(m,n))

空间复杂度：O(Max(m,n))或O(Max(m,n)+1)

2）核心代码：

/**
 * 2：两数之和
 */
public class AddTwoNums {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode target = head;
        ListNode x = l1;
        ListNode y = l2;
        int num1;
        int num2;
        int sum = 0;
        //进位的值
        int carry = 0;
        while (x != null || y != null) {
            //规避某一个链表没有next的情况
            num1 = (x != null) ? x.val : 0;
            num2 = (y != null) ? y.val : 0;
            sum = num1 + num2 + carry;
            carry = sum / 10;
            target.next = new ListNode(sum % 10);
            target = target.next;
            if (x != null) {
                x = x.next;
            }
            if (y != null) {
                y = y.next;
            }
        }
        //排除链表最后一位出现进位的情况
        if (carry > 0) {
            target.next = new ListNode(carry);
        }
        return head.next;
    }
}

3）辅助类：

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        val = x;
        next = null;
    }
    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val + "}";
    }
}