Add Two Numbers (Linked List)

2 Add Two Numbers

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.

1
2
3
4
5

Example:

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

Add Tow Numbers

Problem Analysis

We can not directly turn the input list to the Integer or lang data type since the input might be very long and it will exceed the limits of int or lang. So, we go through each node and record it carries for the next nodes.

Algorithm Analysis

Create a dummy node to record the result. Go through both input lists and sum the value up. If one of the lists meet the end, we assume it’s value is equal to 0. Use a carry variable to record if we need to add 1 to the next nodes and don’t forget to check the value of carrying after traversing two lists.

Time Complexity Analysis

Time: O(N) N is the length of the longer list
Space: O(1)

Code Implementation

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
36
37
38
39
40
41

/**
 * 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) {
        ListNode dummyResult = new ListNode(0);
        /* Used two current pointers to avoid manupulate original lists */
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        ListNode cur = dummyResult;
        int carry = 0;
        
        while(cur1 != null || cur2 != null) {
            /* Calculate the sum of two nodes and carry from the previous calculation */
            int num1 = cur1 == null ? 0 : cur1.val;
            int num2 = cur2 == null ? 0 : cur2.val;
            int sum = num1 + num2 + carry;
            carry = sum / 10;
            sum %= 10;
            
            /* Create a new List Node */
            cur.next = new ListNode(sum);

            /* Move forward those pointers */
            cur = cur.next;
            cur1 = cur1 == null ? null : cur1.next;
            cur2 = cur2 == null ? null : cur2.next;
        }
        /* Check the last digit */
        if(carry != 0) {
            cur.next = new ListNode(carry);
        }
        
        return dummyResult.next;
    }
}

• ← Previous Post
• Next Post →