CareerCup-2.4

You have two numbers represented by a linked list, where each node contains a single digit The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)

Output: 8 -> 0 -> 8

我采用非递归，按照答案的思路写了递归的方法

#include <iostream>
using namespace std;

// Creating a Linked List:
struct Node
{
    Node(int d):data(d){next = NULL;};
    int data;
    Node* next;
};

void printNode(Node* head)
{
    cout<<"Print:"<<endl;
    while(head != NULL)
    {
        cout<<head->data<<endl;
        head = head->next;
    }
    cout<<"End"<<endl;
};

Node* plusNode(Node *o1, Node *o2)
{
    if(o1 == NULL || o2 == NULL)
        return NULL;
    Node *head = new Node(0);
    Node *p = head, *q;
    int temp, flag = 0;
    while(o1 != NULL || o2 != NULL)
    {
        temp = (o1==NULL?0:o1->data) + (o2==NULL?0:o2->data) + flag;
        flag = temp / 10;
        q = new Node(temp % 10);
        p->next = q;
        p = p->next;
        if(o1 != NULL)
            o1 = o1->next;
        if(o2 != NULL)
            o2 = o2->next;
    }
    p->next = NULL;
    p = head->next;
    delete head;
    return p;  
};

Node* plusNodeRec(Node *o1, Node *o2, int carry)
{
    if(o1 == NULL && o2 == NULL)
        return NULL;
    int result = (o1==NULL?0:o1->data) + (o2==NULL?0:o2->data) + carry;
    Node* p = new Node(result % 10);
    Node* next = plusNodeRec(o1==NULL?NULL:o1->next, 
            o2==NULL?NULL:o2->next, result / 10);
    p->next = next;
    return p;
};

int main()
{
    Node* head1 = new Node(3);
    head1->next = new Node(1);
    Node* head2 = new Node(5);
    head2->next = new Node(9);
    head2->next->next = new Node(2);
    // printNode(plusNode(head1, head2));
    printNode(plusNodeRec(head1, head2, 0));
    system("pause"); 
};

CareerCup-2.4

Comments

John Wong @GitHub