[LeetCode] 2. Add Two Numbers

Posted on | In

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

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

Explanation

  1. First create a ListNode with value equals to (l1.val + l2.val)%10, and initialize the carry be (l1.val + l2.val)/10. Also, we need a pointer to point to the last node of the result ListNode.

  2. While l1 or l2 is not NULL, get l1’s value and l2’s value, sum them up plus carry, module 10 to be the next node’s value, update the pointer of the result ListNode and update l1 and l2 to be their next node.

  3. Outside of the while loop, when both l1 and l2 are null, if the carry is not zero, we create a node of the carry’s value and append to the result ListNode.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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) {
        int sum = l1.val + l2.val;
        int val = sum % 10;
        int carry = sum / 10;
        ListNode node = new ListNode(val);
        ListNode cur = node;
        l1 = l1.next;
        l2 = l2.next;
        while (l1 != null || l2 != null) {
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            sum = a + b + carry;
            val = sum % 10;
            carry = sum / 10;
            cur.next = new ListNode(val);
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry == 1) {
            cur.next = new ListNode(carry);
        }
        
        return node;
    }
}