Question

Formatted question description: https://leetcode.ca/all/2.html

2	Add Two Numbers

You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

@tag-linkedlist

Algorithm

Create a new linked list, and then push the input two linked lists from the beginning to the back, add every two, and add a new node to the back of the new linked list.

In order to prevent the two input linked lists from being empty at the same time, we create a dummy node, and add the new nodes generated by the addition of the two nodes to the dummy node in order.

Since the dummy node itself cannot be changed, a pointer is used cur to point to the last node of the new linked list. Ok, you can start to add the two linked lists.

This problem is good because the lowest bit is at the beginning of the linked list, so you can directly add them in order from low to high while traversing the linked list. The condition of the while loop, as long as one of the two linked lists is not an empty row, since the linked list may be empty, when taking the current node value, judge first, if it is empty then value is 0, otherwise take the node value.

Then add the two node values ​​together, and add carry. Then update carry, directly sum/10, and then create a new node with sum%10 as the value, connect it to the back of cur, and then move cur to the next node.

Then update the two nodes, if they exist, point to the next location. After the while loop exits, the highest carry issue needs to be dealt with specially. If carry is 1, then another node with value 1 is created.

Code

Java

  • 
    public class Add_Two_Numbers {
    
    	public class Solution {
    	    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	        if (l1 == null || l2 == null) {
    	            return l1 == null ? l2 : l1;
    	        }
    
    	        // boolean style, 0 or 1
    	        int carry = 0;
    
    	        ListNode dummy = new ListNode(0);
    	        ListNode dummyCopy = dummy;
    
    	        while (l1 != null || l2 != null) {
    	            int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
    
    	            // append to result list
    	            dummy.next = new ListNode(sum % 10);
    	            carry = sum >= 10 ? 1 : 0;
    
    	            // move to next node
    	            l1 = l1 == null ? null : l1.next;
    	            l2 = l2 == null ? null : l2.next;
    	            dummy = dummy.next;
    	        }
    
    	        // @note: I missed final check
    	        if (carry == 1) {
    	            dummy.next = new ListNode(carry);
    	        }
    
    	        return dummyCopy.next;
    	    }
    	}
    
    }
    
  • // OJ: https://leetcode.com/problems/add-two-numbers/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* a, ListNode* b) {
            int carry = 0;
            ListNode dummy, *tail = &dummy;
            while (a || b || carry) {
                if (a) {
                    carry += a->val;
                    a = a->next;
                }
                if (b) {
                    carry += b->val;
                    b = b->next;
                }
                tail->next = new ListNode(carry % 10);
                tail = tail->next;
                carry /= 10;
            }
            return dummy.next;
        }
    };
    
  • # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
      # maybe standard version
      def _addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        p = dummy = ListNode(-1)
        carry = 0
        while l1 and l2:
          p.next = ListNode(l1.val + l2.val + carry)
          carry = p.next.val // 10
          p.next.val %= 10
          p = p.next
          l1 = l1.next
          l2 = l2.next
    
        res = l1 or l2
        while res:
          p.next = ListNode(res.val + carry)
          carry = p.next.val // 10
          p.next.val %= 10
          p = p.next
          res = res.next
        if carry:
          p.next = ListNode(1)
        return dummy.next
    
      # shorter version
      def addTwoNumbers(self, l1, l2):
        p = dummy = ListNode(-1)
        carry = 0
        while l1 or l2 or carry:
          val = (l1 and l1.val or 0) + (l2 and l2.val or 0) + carry
          carry = val // 10
          p.next = ListNode(val % 10)
          l1 = l1 and l1.next
          l2 = l2 and l2.next
          p = p.next
        return dummy.next
    
    

All Problems

All Solutions