[2] Add Two Numbers

© Jarvus Chen / www.jarvus.net

Description

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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Hint: The key point is it will carry into right side digit. And, that may be in the different size of two input lists.

Required knowledge

In this article, you will learn about linked list by C.

Linked lists from http://www.learn-c.org/en/Linked_lists

The only different is declaration method. In this question definition , you have to declare in the following way.

struct ListNode {
    int val;
    struct ListNode *next;
};
struct ListNode* head = malloc(sizeof(struct ListNode));
head->val = 0;
head->next = NULL;

If you want to check is the list with the next node, just check

if ( head == NULL )

You don't have to use

if ( head->next == NULL )

My solution ( Beat 99.15% )

In the middle of my code, if num is larger than 9, overNext represented carry issue will increase. mode control program flow.

• Mode 0 is when two input lists are with next value
• Mode 1 is when List 1 finished and List 2 is with next value
• Mode 2 is when List 2 finished and List 1 is with next value
• Mode 3 is both list finished but there is a carry need to add into right side new digit
• Mode 4 is both list finished and there is no carry left, it can finish the loop and return the result

Another thing is we should return the head address, not the end of the list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {

    struct ListNode* head = malloc(sizeof(struct ListNode));
    struct ListNode* output = head;
    output->next = NULL;

    int num = 0;
    int overNow = 0;
    int overNext  = 0;
    int mode = 0;

    while ( mode < 4 ){

        if ( mode == 0){
            num = l1->val + l2->val;
            l1 = l1->next;
            l2 = l2->next; 
        }else if ( mode == 1){
            num = l2->val;
            l2 = l2->next; 
        }else if ( mode == 2){
            num = l1->val;
            l1 = l1->next;
        }


        num = overNow  + num;
        if ( num > 9){
            num = num - 10;
            overNext  =  1;
        }

        output->val = num;
        overNow = overNext;
        overNext = 0;


        if ( l1 == NULL && l2 != NULL){
            mode = 1;
        }
        if ( l1 != NULL && l2 == NULL){
            mode = 2;
        }
        if ( l1 == NULL && l2 == NULL && overNow != 0){
            mode = 3;
            num = 0;
        }
        if ( l1 == NULL && l2 == NULL && overNow == 0){
            mode = 4;
        }
        if ( mode < 4){
            output->next = malloc(sizeof(struct ListNode));
            output->next->next = NULL;
            output = output->next;
        }

    }

    return head;

}

Others solution

https://discuss.leetcode.com/topic/53867/c-solution-20ms

This is very similar with my concept. However, I only use the basic programming skill to fulfill this problem.

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    struct ListNode* res,*pt,*node;
    int j = 0,temp = 0;
    res = (struct ListNode*) malloc(sizeof(struct ListNode));
    res->next = NULL;
    pt = res;
    while (l1 != NULL || l2 != NULL || j!=0)
    {
        node = (struct ListNode*) malloc(sizeof(struct ListNode));
        temp = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + j;
        node->val = temp%10;
        j = temp/10;
        node->next = NULL;
        pt->next = node;
        pt = node;
        l1 = l1 ? l1->next : l1;
        l2 = l2 ? l2->next : l2;
    }
    pt = res->next;
    free(res);
    return pt;
}