leetcode

LeetCode 2. Add Two Numbers

Problem

LeetCode 2. Add Two Numbers

1. 题目简述

给出两个链表，每个链表表示一个数字，链表中的每个元素表示每一位，从低到高，求两个链表加和（有进位）。例如：

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

2. 算法思路

LeetCode 2的题目，一看就知道也是经典老题了。类似的题目还有LeetCode 445. Add Two Numbers II

这里是从低位到高位，我们需要注意的地方有两点：一是进位二茂铁，二是二者长度不相等的问题，pointer为空的时候要注意。

双指针

两个指针分别指向两个list的初始位置，然后计算是否存在进位，然后计算下一位，如果为空，则为0，继续计算，直至两个pointer均为null且进位也为0.

我们这里有一点需要着重强调，在对链表进行赋值计算的时候，每次对ptr.next进行new，然后将ptr = ptr.next。

时间复杂度:O(m + n)

空间复杂度:O(m + n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode head = new ListNode();
        ListNode ptr1 = l1, ptr2 = l2, ptr = head;
        int flag = 0;

        while (ptr1 != null || ptr2 != null || flag != 0) {
            int value1 = ptr1 == null ? 0 : ptr1.val;
            int value2 = ptr2 == null ? 0 : ptr2.val;
            int value = (value1 + value2 + flag) % 10;
            flag = (value1 + value2 + flag) / 10;

            ptr.next = new ListNode(value);
            ptr = ptr.next;
            ptr1 = ptr1 == null ? null : ptr1.next;
            ptr2 = ptr2 == null ? null : ptr2.next;
        }

        return head.next;
    }
}