StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Wednesday, July 11, 2012

Add two linked lists like integer addition

 July 11, 2012     Programming problems in CPP     No comments   

Write a program to add two linked lists like integer addition without additional data structures

For example, if list 1 contains values 1, 7, 5, 6 as its content nodes and list 2 contains 9, 9, 9 as its content nodes then resultant result is expected to have nodes 2, 7, 5, 5.

The approach:-
  1. The first problem. The lists could be of variable lengths.
  2. The second problem. Integer addition happens from right to left. We cannot use any additional data structures like stacks.
  3. The third problem. We need to support carry.
  4. Easiest solution is to make the linked lists of equal size by pre-pending zeros to the shorter list.
  5. Implement a recursive function which keeps pushing a pair of elements till end of linked list is reached.
  6. On return of the recursive function sum the data elements and previous carry value if any. Also, return the new carry value for the next function call.
  7. Add the new sum element to the final list.

C++ program to add two linked lists like integer addition

#include <iostream>
#include <cmath>
using namespace std;

class Node {
    public:
        Node() { mData = -1; mNext = NULL; }
        ~Node() {}
        int data() { return mData; }
        void setData(int data) { mData = data; }
        Node* next() { return mNext; }
        void setNext(Node* next) { mNext = next; }
    private:
        int mData;
        Node* mNext;
};

class List {
    public:
        List() { mHead = NULL; }

        ~List() {}

        Node* head() { return mHead; }

        void append(int data) {
            Node* tmp = new Node();
            tmp->setData(data);
            if ( mHead == NULL )
                    mHead = tmp;
            else {
                Node* ptr = mHead;
                while ( ptr->next() != NULL ) {
                        ptr = ptr->next();
                }
                ptr->setNext(tmp);
            }
        }

        void prepend(int data) {
            Node* tmp = new Node();
            tmp->setData(data);
            tmp->setNext(mHead);
            mHead = tmp;
        }

        void print() {
            Node* ptr = mHead;
            while ( ptr != NULL ) {
                cout << ptr->data() << " -- ";
                ptr = ptr->next();
            }
            cout << "NULL" << endl;
        }

        int size() {
            Node* ptr = mHead;
            int count = 0;
            while ( ptr != NULL ) {
                count++;
                ptr = ptr->next();
            }
            return count;
        }

    private:
        Node* mHead;
};

int addlists1(Node* node1, Node* node2, List* l3) {
    if ( node1 == NULL ) return 0;
    int carry = addlists1(node1->next(), node2->next(), l3);
    int val = carry + node1->data() + node2->data();
    int carry1 = val / 10;
    int nodeval = val % 10;

    l3->prepend(nodeval);

    return carry1;
}

void addlists(List* l1, List* l2, List* l3) {
    int size1 = l1->size();
    int size2 = l2->size();
    int diff = size1 - size2;
    if ( size1 > size2 ) {
        while ( diff > 0 ) {
            l2->prepend(0);
            diff--;
        }
    }
    else if ( size2 > size1 ) {
        while ( diff > 0 ) {
            l1->prepend(0);
            diff--;
        }
    }

    cout << "After prepending zeros." << endl;
    l1->print();
    l2->print();

    int carry = addlists1(l1->head(), l2->head(), l3);
    if ( carry ) {
       l3->prepend(carry);
    }
}

int main() {
    List* l1 = new List();
    l1->append(1);
    l1->append(7);
    l1->append(5);
    l1->append(6);

    List* l2 = new List();
    l2->append(9);
    l2->append(9);
    l2->append(9);

    cout << "Initial lists." << endl;
    l1->print();
    l2->print();

    List* l3 = new List();
    addlists(l1, l2, l3);

    cout << "Summed up list." << endl;
    l3->print();

    delete l1;
    delete l2;
}
Output:-
1 -- 7 -- 5 -- 6 -- NULL
9 -- 9 -- 9 -- NULL
After prepending zeros.
1 -- 7 -- 5 -- 6 -- NULL
0 -- 9 -- 9 -- 9 -- NULL
Summed up list.
2 -- 7 -- 5 -- 5 -- NULL
Email ThisBlogThis!Share to XShare to Facebook
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Python FastAPI file upload and download
    In this article, we will look at an example of how to implement a file upload and download API in a Python FastAPI microservice. Example bel...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Accessing the Kubernetes API
    In this article, we will explore the steps required to access the Kubernetes API and overcome common challenges. All operations and communic...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Scheduling jobs in Python
    When developing applications and microservices we run into scenarios where there is a need to run scheduled tasks. Examples include performi...
  • Using Tekton to deploy KNative services
    Tekton is a popular open-source framework for building continuous delivery pipelines. Tekton provides a declarative way to define pipelines ...

Copyright © StackStalk