「每日一道算法题」Add Two Numbers

OJ address

OJ website : 2. Add Two Numbers

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.

Example:

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

Solution in C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* insertList(char *string) {
    struct ListNode* newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
    newNode->next = 0;
    newNode->val = 0;
    struct ListNode* headNode = newNode;
    int flag = 0;
    for(int i=0;i<strlen(string);++i) {
        if (flag == 0) {
            newNode->val = string[i]-'0';
            flag = 1;
        }
        else {
            struct ListNode* nextNode = (struct ListNode *)malloc(sizeof(struct ListNode));
            nextNode->val = string[i]-'0';
            nextNode->next = 0;
            newNode->next = nextNode;
            newNode = nextNode;
        }
    }
    return headNode;
}

void printNode(struct ListNode *listNode) {
    while(listNode) {
        printf("%d", listNode->val);
        listNode = listNode->next;
    }
    printf("\n");
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
    newNode->next = 0;
    newNode->val = 0;
    struct ListNode* headNode = newNode;
    int flag = 0;
    while(l1 || l2 || flag) {
        int a = 0;
        int b = 0;
        int sum = 0;
        int mark = 0;
        a = l1 ? l1->val : 0;
        b = l2 ? l2->val : 0;
        sum = a+b+flag;
        flag = sum/10;
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
        struct ListNode* nextNode = (struct ListNode *)malloc(sizeof(struct ListNode));
        nextNode->val = sum%10;
        nextNode->next = 0;
        newNode->next = nextNode;
        newNode = nextNode;
    }
    return headNode->next;
}

int main(int argc, char const *argv[])
{
    char *ch = "12345\0";
    char *ch1 = "912345\0";
    struct ListNode *listA = insertList(ch);
    struct ListNode *listB = insertList(ch1);
    struct ListNode *listC = addTwoNumbers(listA,listB);
    printNode(listA);
    printNode(listB);
    printNode(listC);
    return 0;
}

Solution in Python

# Definition for singly-linked list.
#!/usr/bin/python3
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):

    def initData(self, str):
        t = len(str)
        flag = 0
        ret = ListNode(int(str[0]))
        dd = ret
        for i in xrange(1,t+1):
            if flag == 0:
                flag = 1
            else:
                ret.next = ListNode(int(str[i-1]))
                ret = ret.next
        return dd 

    def printNode(self, l):
        while l:
            print l.val,
            l = l.next
        print ' '


    def addTwoNumbers(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        ret = ListNode(0)
        dd = ret
        flag = 0
        while l1 or l2 or flag:
            mark = 0
            if l1:
                a = l1.val
                l1 = l1.next
            else :
                a = 0
            if l2:
                b = l2.val 
                l2 = l2.next
            else :
                b = 0
            ddsum = a + b + flag
            flag = ddsum / 10
            ret.val = ddsum%10
            if l1 :
                mark = 1
            if l2 :
                mark = 1
            if flag:
                mark = 1
            if mark:
                ret.next = ListNode(0)
                ret = ret.next
        return dd


if __name__ == '__main__':
    a = Solution()
    b = a.initData('5')
    c = a.initData('5')
    a.printNode(b)
    a.printNode(c)
    d = a.addTwoNumbers(b,c)
    a.printNode(d)

My Idea

注意一下加法进位和两个链表可能长度不同的问题。