Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

2. Add two numbers

You are given two non-empty linked lists representing two non-negative integers. Each digit is stored in reverse order, and only one digit can be stored per node.

You add the two numbers and return a linked list representing the sum in the same form.

You can assume that neither of these numbers will start with 0, except for the number 0.

Thought analysis

The reason we deliberately reverse the list is because we add and carry, and carry must be done in order, so we need to traverse from the lowest to the highest.

Also, if the list length is different, then if the list is sequential from high to low, then the “alignment” operation is required, but if the list is reversed, then the alignment operation can be omitted.

To sort out the ideas:

  • First, add and carry
  • Then get the value of the new node based on and % 10
  • Repeat the above operation

There are code:

// Both l1 and L2 are not traversed
while(l1 || l2){
    // add and carry
    int n1 = l1 ? l1->val: 0;
    int n2 = l2 ? l2->val: 0;
    int sum = n1 + n2 + carry;
    carry = sum / 10;
     if(! head) {/ / initialization
        head = tail = new ListNode(sum % 10);
    } else {
    // Set the next node
        tail->next = new ListNode(sum % 10);
        tail = tail->next;
    }
    if(l1)l1 = l1->next;
    if(l2)l2 = l2->next;

}
// Determine whether the carry needs to be incremented by 1
if (carry == 1){
    tmp = l3.next;
    tmp.val = carry;
    tmp.next = null;
    
}

Copy the code