Magic complement 0 solution to add linked list: LeeCode002 two numbers add

Topic describes

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

If we add these two numbers together, a new linked list is returned to represent their sum.

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

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) output:7 -> 0 -> 8The reason:342 + 465 = 807
Copy the code

Solution 1: violence calculation

This method uses the method of adding numbers to calculate, but a fatal problem of this method is integer overflow. So, strictly speaking, this approach is wrong. The code is as follows:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}};int listNodeLength(ListNode *list) {
    if (list= =NULL || list->next == NULL)
    {
        return 0;
    }
    
    int size = 0;
    ListNode *tmpPoint = list;
    while(tmpPoint->next ! =NULL) {
        size++;
        tmpPoint = tmpPoint->next;
    }
    return size;
}


class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int sum1 = getListSum(l1);
        int sum2 = getListSum(l2);
        int sum3 = sum1 + sum2;
        
        int sum3Length = 0;
        int tmp = sum3;
        while(tmp > 0) {
            tmp = tmp/10;
            sum3Length++;
        }
        
        ListNode *head = NULL;
        ListNode *tail = nullptr;
        int m = sum3;
        while(sum3Length > 0) {
            int val = m%(10);
            m = m / 10;
            
            ListNode *list = new ListNode(val);
            if (head)
            {
                tail->next = list;
                tail = list;
            } else {
                head = list;
                tail = head;
            }
            sum3Length--;
        }
        return head;
        
    }
    
    int getListSum(ListNode *list) {
        int length = listNodeLength(list);
        
        int sum = 0;
        int index = 0;
        ListNode *tmpPoint = list;
        while(tmpPoint ! =NULL) {
            sum += pow(10, length-index) * tmpPoint->val;
            tmpPoint = tmpPoint->next;
            index++;
        }
        
        returnsum; }};Copy the code

Solution two: calculate by bit

The solution uses a variable to represent the carry value. In the following figure, temp indicates the carry. Change the length of two lists to be the same by adding 0.

The specific code is as follows:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}};int listNodeLength(ListNode *list) {
    if (list= =NULL)
    {
        return 0;
    }
    
    int size = 0;
    ListNode *tmpPoint = list;
    while(tmpPoint ! =NULL) {
        size++;
        tmpPoint = tmpPoint->next;
    }
    return size;
}


class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int l1Length = listNodeLength(l1);
        int l2Length = listNodeLength(l2);
        
        int max = l1Length;
        ListNode *maxListNode = l1;
        int min = l2Length;
        ListNode *minListNode = l2;
        if (l1Length<l2Length)
        {
            max = l2Length;
            maxListNode = l2;
            
            min = l1Length;
            minListNode = l1;
        }
        
        ListNode *minTail = minListNode;
        ListNode *maxTail = maxListNode;
        while(maxTail ! =NULL) {
            if (minTail -> next == NULL) {
                minTail->next = new ListNode(0);
            }
            maxTail = maxTail -> next;
            minTail = minTail->next;
        }
        
        int temp = 0;
        ListNode* l1temp = minListNode;
        ListNode* l2temp = maxListNode;
        ListNode *result = NULL;
        ListNode *resultTail = NULL;
        for (int i = 0; i < max; ++i)
        {
            int sum = l1temp->val + l2temp->val + temp;
            temp = sum/10;
            int val = sum%10;
            ListNode *node = new ListNode(val);
            if (result == NULL)
            {
                result = node;
                resultTail = result;
            }
            else
            {
                resultTail->next = node;
                resultTail = node;
            }
            
            l1temp = l1temp->next;
            l2temp = l2temp->next;
        }
        
        if (temp > 0) {
            resultTail->next = new ListNode(temp);
        }
        returnresult; }};Copy the code

The source code

You can get the source code here: LeeCodeTrain

discuss

I posted the solutions to the questions on my blog: Riverli. me and my wechat account.

Welcome you to pay attention to my public account, discuss: algorithm, front-end, iOS, Android, user experience, architecture, programmer development and other content.