Add Two Numbers

Question

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

Answer 1

// The most concise code ever
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode iter1 = l1, iter2 = l2;
    ListNode list = null, tail = null;

    int carry = 0;
    while (iter1 != null || iter2 != null || carry != 0) {
        int num1 = iter1 == null ? 0 : iter1.val;
        int num2 = iter2 == null ? 0 : iter2.val;
        int sum = num1 + num2 + carry;
        carry = sum / 10;
        sum %= 10;
        if (list == null) {
            list = new ListNode(sum);
            tail = list;
        } else {
            tail.next = new ListNode(sum);
            tail = tail.next;
        }

        iter1 = iter1 == null ? null : iter1.next;
        iter2 = iter2 == null ? null : iter2.next;
    }

    return list;
}

Answer 2

class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    ListNode *head = new ListNode(0); //dummy node to avoid judging if head is NULL
    ListNode *tail = head;
    int carry = 0;
    ListNode *p1 = l1;
    ListNode *p2 = l2;
    ListNode *node;
    while (p1 && p2) { //add the common nodes with carry
        node = new ListNode(p1->val + p2->val + carry);
        carry = (node->val >= 10) ? 1 : 0;
        node->val %= 10;
        tail->next = node;
        tail = node;
        p1 = p1->next;
        p2 = p2->next;
    }

    if (p1) {
        copyList(tail, p1, carry);
    } else if (p2) {
        copyList(tail, p2, carry);
    } else {
        if (carry > 0) {
            node = new ListNode(carry);
            tail->next = node;
            tail = node;
        }
    }
    node = head;
    head = head->next;
    delete node; //delete dummy node
    return head;
}
private:
void copyList(ListNode *tail, ListNode *pSrc, int carry) //merge the left nodes with carry
{
    ListNode *node;
    while (pSrc) {
        node = new ListNode(pSrc->val + carry);
        carry = (node->val >= 10) ? 1 : 0;
        node->val %= 10;
        tail->next = node;
        tail = node;
        pSrc = pSrc->next;
    }
    if (carry > 0) {
        node = new ListNode(carry);
        tail->next = node;
        tail = node;
    }
}
};

Answer 3

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    ListNode *s = new ListNode(0);
    ListNode *c = s;
    bool f1 = (NULL != l1);
    bool f2 = (NULL != l2);
    while(1) {
        if(f1) {
            c->val += l1->val;
            l1 = l1->next;
            f1 = (NULL != l1);
        }
        if(f2) {
            c->val += l2->val;
            l2 = l2->next;
            f2 = (NULL != l2);
        }
        bool carry = c->val / 10;
        c->val %= 10;
        if(f1 || f2 || carry) {
            c->next = new ListNode(carry);
            c = c->next;
        } else
            break;
    }
    return s;
}

Answer 4

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;

        int base = 0;
        ListNode *rsthead = NULL;
        ListNode *rsttail = rsthead;
        ListNode *tmp;
        while(l1 != NULL && l2 != NULL) {
            tmp = new ListNode((l1->val + l2->val + base) % 10);
            base = (l1->val + l2->val + base) / 10;
            if(rsttail != NULL) {
                rsttail->next = tmp;
                rsttail = tmp;
            } else {
                rsthead = rsttail = tmp;
            }
            l1 = l1->next;
            l2 = l2->next;
        }

        ListNode *notept;
        if(l1 != NULL || l2 != NULL) {
            notept = (l1 == NULL)?(l2):(l1);
            while(notept != NULL) {
                tmp = new ListNode((notept->val + base) % 10);
                base = (notept->val + base) / 10;
                rsttail->next = tmp;
                rsttail = tmp;
                notept = notept->next;
            }           
        }
        if(base > 0) {
            tmp = new ListNode(base);
            rsttail->next = tmp;
        }
        return rsthead;
    }
};

Answer 5

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int carry = 0;
    ListNode rootListNode = new ListNode(-1);
    ListNode currentListNode = rootListNode;

    while (l1 != null || l2 != null) {
        int sum = carry;
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }

        if (sum >= 10) {
            carry = 1;
            sum -= 10;
        } else {
            carry = 0;   
        }
        currentListNode.next = new ListNode(sum);
        currentListNode = currentListNode.next;
    }
    if (carry == 1) {
        currentListNode.next = new ListNode(carry);
    }

    return rootListNode.next;
}

Answer 6

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *head = 0;
ListNode *pNew = 0;
ListNode *temp = 0;
int jinWei =0;
int val = 0;
while (l1 != 0 && l2 != 0) {
    val = l2->val + l1->val + jinWei;
    if (val >= 10) {
        jinWei = val / 10;
        val = val - 10;
    }
    else
    {
        jinWei = 0 ;
    }
    pNew = new ListNode(val);
    if (head == 0) {
        head = temp = pNew;
    }
    else{
        temp->next = pNew;
        temp = pNew;
    }
    l1 = l1->next;
    l2 = l2->next;
}
while (l1 != 0) {
    val = l1->val + jinWei;
    if(val>=10){
        jinWei = val/10;
        val = val - 10;
    }
    else
        jinWei = 0;
    pNew = new ListNode(val);
    temp->next = pNew;
    temp = pNew;
    l1=l1->next;
}
while (l2 != 0) {
    val = l2->val + jinWei;
    if(val>=10){
        jinWei = val/10;
        val = val - 10;
    }
    else
        jinWei = 0;
    pNew = new ListNode(val);
    temp->next = pNew;
    temp = pNew;
    l2 = l2->next;
}
if(jinWei != 0)
{
    pNew = new ListNode(jinWei);
    temp->next = pNew;
}
return head;

}

Answer 7

class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    if (!l1 && !l2)
        return new ListNode(0);

    ListNode *p  = l1, *q = l2;
    ListNode *head = new ListNode(0), *phead = head;
    int adv = 0;
    while(p && q) {
        int value = p->val + q->val + adv;
        adv = value / 10;
        phead->next = new ListNode(value%10);
        phead = phead->next;
        p = p->next;
        q = q->next;
    }
    if (p) {
        while(p) {
            int value = p->val + adv;
            adv = value / 10;
            phead->next = new ListNode(value%10);
            phead = phead->next;
            p = p->next;
        }
    }
    if (q) {
        while(q) {
            int value = q->val + adv;
            adv = value / 10;
            phead->next = new ListNode(value%10);
            phead = phead->next;
            q = q->next;
        }
    }
    while(adv>0) {
        phead->next = new ListNode(adv%10);
        phead = phead->next;
        adv /= 10;
    }

    if (head->next) {
        ListNode *dum = head;
        head = head->next;
        delete dum;
    }
    return head;
}
};

Answer 8

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

    ListNode *head, *l12, *p; 
    head =new ListNode(0); 
    int bitB=0, bitA, Indexhead=0; 
    int l1val, l2val; 
    while(l1!=NULL || l2!=NULL) 
    {
     if(l1!=NULL) l1val=l1->val;
     else l1val=0; 
     if(l2!=NULL) l2val=l2->val;
     else l2val=0;
     bitA=(l1val+l2val+bitB)/10;
     if(Indexhead==0) { head->val+=l1val+l2val+bitB-bitA*10; Indexhead=1; p=head; }
     else {
          l12=new ListNode(0);               
          l12->val+=l1val+l2val+bitB-bitA*10;
          p->next=l12; 
          p=l12; 
         } 
     bitB=bitA;
     if(l1!=NULL) l1=l1->next; if(l2!=NULL) l2=l2->next; 
    }
    if(bitB==1) { l12=new ListNode(1); 
                 p->next=l12; p=l12; 
    }

    return head; 
}

};

Answer 9

/ * Definition for singly-linked list. * struct ListNode { * int val; * ListNode next; * ListNode(int x) : val(x), next(NULL) {} * }; / class Solution { public: void ReverseLL(ListNode headNode) { ListNode prev = NULL; ListNode temp1 = headNode; ListNode temp2 = headNode->next;

    while(temp2 != NULL)
    {
        temp1->next = prev;
        prev = temp1;
        temp1 = temp2;
        temp2 = temp2->next;
    }
    headNode = temp1;
}
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    if(!l1 && !l2)
    {
        return NULL;
    }

    if(!l1)
    {
        //ReverseLL(l2);
        return l2;
    }

    if(!l2)
    {
        //ReverseLL(l1);
        return l1;
    }

    ListNode *firstLL = l1;
    long long first_int = 0;
    long long factor = 1;
    while(firstLL)
    {
        first_int = first_int + factor*firstLL->val;
        factor = factor*10;
        firstLL = firstLL->next;
    }

    ListNode *secLL = l2;
    long long sec_int = 0;
    factor = 1;
    while(secLL)
    {
        sec_int = sec_int + factor*secLL->val;
        factor = factor*10;
        secLL = secLL->next;
    }

    long long finalnum = first_int + sec_int;

    if(finalnum == 0)
    {
        ListNode* node = new ListNode(0);
        return node;
    }

    ListNode *head;
    ListNode *last_node;
    bool first_time = true;

    while(finalnum != 0)
    {
        long long node_val = finalnum %10;
        finalnum = finalnum / 10;
        ListNode *node;
        if(first_time)
        {
            node = new ListNode(node_val);
            head = node;
            node->val = node_val;
            node->next = NULL;
            first_time = false;
        }
        else
        {
            node = new ListNode(node_val);
            last_node->next = node;
            node->val = node_val;
            node->next = NULL;
        }
        last_node = node;

    }

    return head;

}

};

Answer 10

package LinkedListStuff;

class Node { int data; Node link;

public Node(int val) {
    data = val;
    link = null;
}

}

public class AddTwoNumbers { public Node AddTwoNumbers(Node num1, Node num2) { if (num1 == null) return num2; else if (num2 == null) return num1;

    int carry = 0;
    Node result = null;
    Node navi = null;
    Node temp = null;
    while (num1 != null) {
        if (num2 != null) {
            if (num1.data + num2.data + carry >= 10) {
                temp = new Node(num1.data + num2.data + carry - 10);
                carry = (num1.data + num2.data + carry) / 10;
                if (navi != null) {
                    navi.link = temp;
                    navi = navi.link;
                }
            } else {
                temp = new Node(num1.data + num2.data + carry);
                carry = 0;
                if (navi != null) {
                    navi.link = temp;
                    navi = navi.link;
                }
            }
            if (result == null) {
                navi = temp;
                result = temp;
            }
            num1 = num1.link;
            num2 = num2.link;
        } else {
            break;
        }
    }
    while (num2 != null) {
        if (num2.data + carry >= 10) {
            carry = (num2.data + carry) / 10;
            temp = new Node(num2.data + carry - 10);
            navi.link = temp;

        } else {
            temp = new Node(num2.data + carry);
            carry = 0;
            navi.link = temp;
        }
        num1 = num1.link;
        num2 = num2.link;
        navi = navi.link;
    }
    return result;
}

public static void main(String args[]) {
    Node num1 = new Node(1);
    Node num2 = new Node(2);
    Node num3 = new Node(3);
    Node num4 = new Node(4);

    Node num5 = new Node(9);
    Node num6 = new Node(9);
    Node num7 = new Node(3);
    Node num8 = new Node(4);
    num1.link = num2;
    num2.link = num3;
    num3.link = num4;
    num5.link = num6;
    num6.link = num7;
    num7.link = num8;
    AddTwoNumbers adt = new AddTwoNumbers();
    Node result = adt.AddTwoNumbers(num1, num5);
    System.out.println("Coming Here :: ");
    while (result != null) {
        System.out.println("Sum is :: " + result.data);
        result = result.link;
    }
}

}

Add Two Numbers

Follow this question

Welcome to LeetCode

Related questions