C + + implementation of adding two numbers of leetcode topics

I. Title Description

Original title link: https://leetcode-cn.com/problems/add-two-numbers

Two non empty linked lists are given to represent two non negative integers. Their respective digits are stored in reverse order, and each node can only store one digit.

If we add the two numbers together, we will return a new linked list to represent their sum.

You can assume that neither of these numbers starts with 0 except for the number 0.

Example:

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

II. Topic analysis

This topic mainly studies two knowledge points big number addition and chain list. The general idea is to simulate the process of adding two numbers.

When primary school students are just learning mathematics, how to add many numbers? That is, from the beginning of a single digit, add one bit by one, and carry if it is greater than 10.

This topic uses the form of linked list to study the addition of large numbers, so it will be difficult, especially for people who are not familiar with linked list.

There are three points to pay attention to when writing code:

  • The length of two linked lists is different
  • Linked list is empty.
  • carry

C + + code

Passed the test on leetcode website

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode *l3, *cur1, *cur2, *cur3, *temp;
        int carry_flag = 0; // carry

        l3 = temp = cur3 = NULL;
        cur1 = l1; cur2 = l2;

        while (cur1 != NULL || cur2 !=NULL) {

            temp = new ListNode(0);
            temp->next = NULL;

            if(cur1 == NULL && cur2 != NULL){
                // The link list l1 is empty. At this time, l1 does not need to move back, and only needs to add link list l2 to sum.
                temp->val = cur2->val + carry_flag;
                cur2 = cur2->next;
            }
            else if(cur2 == NULL && cur1 != NULL){
                // The link list l2 is empty. At this time, l2 does not need to move back, and the sum only needs to add the link list l1.
                temp->val = cur1->val + carry_flag;
                cur1 = cur1->next;
            }
            else{
                temp->val = cur1->val + cur2->val + carry_flag;
                cur2 = cur2->next; cur1 = cur1->next;
            }

            carry_flag = temp->val / 10;
            temp->val = temp->val % 10;

            // Assign the sum result to the return result list l3
            if(l3 == NULL)
                l3 = temp;
            else
                cur3->next = temp;

            cur3 = temp;
        }

        // If the last sum result is greater than or equal to 10, you need to add a new node after l3 to save carry
        if(carry_flag == 1){
            temp = new ListNode(1);
            temp->next = NULL;

            cur3->next = temp;
        }

        return l3;
    }
};

Posted on Sat, 02 Nov 2019 02:16:42 -0700 by interface