Add two numbers represented by linked list

Add two numbers represented by linked lists

Here given code implementation process.

//C Program
//Add two numbers represented by linked list
//Assume each node of linked list contains a single digit integer value
#include <stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node
{
  int data;
  struct Node*next;
};

//insert Node element
void insert(struct Node**head,int value)
{
  //Create dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL)
  {
    printf("Memory overflow\n");
  }else
  {
    node->data=value;
    node->next=NULL;
    if(*head==NULL)
    {
      *head=node;
    }else
    {

      struct Node*temp=*head;
      //find last node
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add node at last possition
      temp->next=node;
    }
  }
}
//Display element of Node
void display(struct Node*temp)
{
  
  if(temp==NULL)
  {
    printf("Empty linked list");
  }
  while(temp!=NULL)
  {
    printf("%d  ",temp->data);
    temp=temp->next;
  }
}

//reverse a single linked list
struct Node* reverse(struct Node*head)
{
 
  struct Node*prev=NULL,*temp=head;
  while(temp!=NULL){
    //new head node
    (head)=temp;
      
    //visit to next node
    temp=temp->next;
    //change node link to pervious node
    (head)->next=prev;
    //get the reference of newly head node
    prev=(head);
  }
  return head;
  

}

//create new node of linked list
struct Node*make_node(int data)
{
  struct Node*auxiliary=NULL;

  auxiliary=(struct Node*)malloc(sizeof(struct Node));
  
  if(auxiliary!=NULL)
  {
    auxiliary->next=NULL;
    auxiliary->data=data;
  }

  return auxiliary;
}

struct Node* add_nodes(struct Node*head1 ,struct Node*head2)
{

  if(head2==NULL)
  {
    return head1;
  }
  else if(head1==NULL) 
  {
   
    return head2;
  }
  else
  {
    head1 = reverse(head1);
    head2 = reverse(head2);

    struct Node*auxiliary=NULL,*head=head1,*current=NULL;
    int carry = 0;
    while(head1!=NULL || head2 != NULL)
    {
      if(head1!=NULL && head2!=NULL)
      {
        current=head1;
        carry += head1->data + head2->data;

        if(carry<10)
        {
          head1->data = carry;
          carry=0;
        }
        else
        {
          head1->data = carry%10;
          carry/=10;
        }
        head1=head1->next;
        auxiliary=head2;
        head2=head2->next;  

        free(auxiliary);
        auxiliary=NULL;
      }
      else if(head1!=NULL)
      {
        current=head1;
        carry+=head1->data;

        if(carry < 10)
        {
          head1->data = carry;
          carry=0;
        }
        else
        {
          head1->data = carry%10;
          carry /= 10;
        }
        head1=head1->next;
      }
      else if(head2 != NULL)
      {
        current->next=head2;
        current=head2;

        carry+=head2->data;

        if(carry < 10)
        {
          head2->data = carry;
          carry=0;
        }
        else
        {
          head2->data = carry%10;
          carry /= 10;
        }
        head2=head2->next;
      }

    }
    while(carry!=0)
    {
      current->next=make_node(carry%10);
      carry/=10;
      current=current->next;
    }
    head=reverse(head); 
    return head;
  }
}

int main()
{
  //create node pointer
  struct Node*head1=NULL,*head2=NULL;

  //5112

  insert(&head1,5);
  insert(&head1,1);
  insert(&head1,1);
  insert(&head1,2);

  //99999
  insert(&head2,9);
  insert(&head2,9);
  insert(&head2,9);
  insert(&head2,9);
  insert(&head2,9);

  head1=add_nodes(head1,head2);
  head2=NULL;
  //display all node
  display(head1);
  return 0;
}

Output

1  0  5  1  1  1
//C++ Program 
//Add two numbers represented by linked list
#include <iostream>
using namespace std;

//Create structure
struct Node
{
  int data;
  struct Node*next;
};
class LinkedList
{

public:
  Node*head;//head node
  LinkedList();
  void insert(int);
  void display();
  Node*make_node(int);
  void reverse();
  void add_nodes(LinkedList);
};
LinkedList::LinkedList()
{
  head=NULL;
}
//insert node at end of linked list
void LinkedList::insert(int value)
{
  //Create dynamic node
  Node*node=new Node;
  if(node==NULL)
  {
    cout<<"Memory overflow\n";
  }else
  {
    node->data=value;
    node->next=NULL;
    if(head==NULL)
    {
      //base condition
      head=node;
    }else
    {
      Node*temp=head;
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }
      //add newly node at last
      temp->next=node;
    }
  }
}
//display all node value in linked list
void LinkedList:: display()
{
  if(head==NULL)
  {
    cout<<"Empty linked list";
  }
  else
  {
    Node*temp=head;
    cout<<"Linked List : ";
    while(temp!=NULL)
    {
      //print node value
      cout<<temp->data<<" ";
      temp=temp->next;
    }
  }
}
//reverse a single linked list
void LinkedList:: reverse()
{
 
   Node*prev=NULL,*temp=head;
  while(temp!=NULL)
  {
    //new head node
    (head)=temp;
      
    //visit to next node
    temp=temp->next;
    //change node link to pervious node
    head->next=prev;
    //get the reference of newly head node
    prev=head;
  }
}

//create new node of linked list
Node* LinkedList:: make_node(int data)
{
  Node*auxiliary = NULL;

  auxiliary = new Node;
  
  if(auxiliary != NULL)
  {
    auxiliary->next = NULL;
    auxiliary->data = data;
  }

  return auxiliary;
}

void LinkedList :: add_nodes(LinkedList obj2)
{

  if(obj2.head == NULL )
  {
    return;
  }
  else if( this->head == NULL ) 
  {
   
    this->head = obj2.head;
    obj2.head = NULL;
  }
  else
  {
    this->reverse();
    obj2.reverse();

    Node * auxiliary = NULL,*head1=head,*current=NULL;
    int carry = 0;
    while(head1 != NULL || obj2.head != NULL)
    {
      if(head1 != NULL && obj2.head != NULL)
      {
        current = head1;
        carry += head1->data + obj2.head->data;

        if(carry<10)
        {
          head1->data = carry;
          carry=0;
        }
        else
        {
          head1->data = carry%10;
          carry/=10;
        }
        head1 = head1->next;
        auxiliary = obj2.head;
        obj2.head = obj2.head->next;  

        delete (auxiliary);
        auxiliary = NULL;
      }
      else if(head1 != NULL)
      {
        current = head1;
        carry += head1->data;

        if(carry < 10)
        {
          head1->data = carry;
          carry=0;
        }
        else
        {
          head1->data = carry%10;
          carry /= 10;
        }
        head1 = head1->next;
      }
      else if(obj2.head != NULL)
      {
        current->next = obj2.head;
        current = obj2.head;

        carry += obj2.head->data;

        if(carry < 10)
        {
          obj2.head->data = carry;
          carry=0;
        }
        else
        {
          obj2.head->data = carry%10;
          carry /= 10;
        }
        obj2.head=obj2.head->next;
      }

    }
    while(carry != 0)
    {
      current->next = make_node(carry%10);
      carry/=10;
      current = current->next;
    }
    this->reverse(); 
   
  }
}
int main()
{

  //create object
  LinkedList obj1,obj2;

  //5112

  obj1.insert(5);
  obj1.insert(1);
  obj1.insert(1);
  obj1.insert(2);

  //99999
  obj2.insert(9);
  obj2.insert(9);
  obj2.insert(9);
  obj2.insert(9);
  obj2.insert(9);

  obj1.add_nodes(obj2);
  obj1.display();
  return 0;
}

Output

Linked List : 1 0 5 1 1 1
//Java program
//Add two numbers represented by linked list
public class LinkedList
{

  static class Node
  {
    int data;
    Node next;
  }
  public Node head;
  //Class constructors
  LinkedList()
  {
    head=null;
  } 
  //insert  element
  public void insert(int value)
  {
    //Create  node
    Node node=new Node();
    node.data=value;
    node.next=null;
    if(head==null) head=node;
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=node;
    }
    
  }
  //Display all Linked List elements
  public void display()
  {
    if(head!=null)
    {
      System.out.print("Linked List Element :");
      Node temp=head;
      while(temp!=null)
      {
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
      System.out.println();
    }else
    {
      System.out.println("Empty Linked list"); 
    }
  }
  //reverse a single linked list
public void reverse()
{
 
  Node prev=null, temp=head;
  while(temp!=null)
  {
    //new head node
    head=temp;
      
    //visit to next node
    temp=temp.next;
    //change node link to pervious node
    head.next=prev;
    //get the reference of newly head node
    prev=head;
  }
}

//create new node of linked list
public Node  make_node(int data)
{
  Node auxiliary = null;

  auxiliary = new Node();
  
  
  auxiliary.next = null;
  auxiliary.data = data;
  

  return auxiliary;
}

public void add_nodes(LinkedList obj2)
{

  if(obj2.head == null )
  {
    return;
  }
  else if( this.head == null ) 
  {
   
    this.head = obj2.head;
    obj2.head = null;
  }
  else
  {
    this.reverse();
    obj2.reverse();

    Node  auxiliary = null, head1=head, current=null;
    int carry = 0;
    while(head1 != null || obj2.head != null)
    {
      if(head1 != null && obj2.head != null)
      {
        current = head1;
        carry += head1.data + obj2.head.data;

        if(carry<10)
        {
          head1.data = carry;
          carry=0;
        }
        else
        {
          head1.data = carry%10;
          carry/=10;
        }
        head1 = head1.next;
        auxiliary = obj2.head;
        obj2.head = obj2.head.next;  

        auxiliary = null;
      }
      else if(head1 != null)
      {
        current = head1;
        carry += head1.data;

        if(carry < 10)
        {
          head1.data = carry;
          carry=0;
        }
        else
        {
          head1.data = carry%10;
          carry /= 10;
        }
        head1 = head1.next;
      }
      else if(obj2.head != null)
      {
        current.next = obj2.head;
        current = obj2.head;

        carry += obj2.head.data;

        if(carry < 10)
        {
          obj2.head.data = carry;
          carry=0;
        }
        else
        {
          obj2.head.data = carry%10;
          carry /= 10;
        }
        obj2.head=obj2.head.next;
      }

    }
    while(carry != 0)
    {
      current.next = make_node(carry%10);
      carry/=10;
      current = current.next;
    }
    this.reverse(); 
   
  }
}
  public static void main(String[] args) 
  {

    LinkedList obj1 = new LinkedList();
    LinkedList obj2 = new LinkedList();
   
    //5112
    obj1.insert(5);
    obj1.insert(1);
    obj1.insert(1);
    obj1.insert(2);

    //99999
    obj2.insert(9);
    obj2.insert(9);
    obj2.insert(9);
    obj2.insert(9);
    obj2.insert(9);

    obj1.add_nodes(obj2);
    obj1.display();
  }
}

Output

Linked List Element :  1  0  5  1  1  1
#Python Program 
#Add two numbers represented by linked list
class Node:
  def __init__(self,data):
    self.data=data
    self.next=None

#create class Linked    
class LinkedList:

  def __init__(self):

    #Assign default value
    self.head=None

  #insert new node to Linked  
  def insert(self,data):

    node=Node(data)

    if(self.head==None):
      #first element of linked list
      self.head=node
    else:
    
      temp=self.head
      #find middle node of linked list
      while(temp!=None and temp.next!=None ):
        temp=temp.next
      
      #add at last of linked list  
      temp.next=node 
   

  #display all linked list node 
  def display(self):
    temp=self.head
    while(temp!=None):
      print(temp.data,end=" ")
      temp=temp.next
    print()

  
  def reverse(self):
 
    prev=None
    temp=self.head
    while(temp!=None):

      #new head node
      self.head=temp
        
      #visit to next node
      temp=temp.next
      #change node link to pervious node
      self.head.next=prev
      #get the reference of newly head node
      prev=self.head
    


  #create new node of linked list
  def make_node(self, data):

    auxiliary = None

    auxiliary = Node(data)
    
    return auxiliary



  def add_nodes(self,obj2):

    if(obj2.head == None ):
      return;
    
    elif( self.head == None ) :
     
      self.head = obj2.head;
      obj2.head = None;
    
    else:
      self.reverse();
      obj2.reverse();

      auxiliary = None
      head1=self.head
      current=None
      carry = 0
      while(head1 != None or obj2.head != None):

        if(head1 != None and obj2.head != None):
          
          current = head1;
          carry += head1.data + obj2.head.data;

          if(carry<10):
            head1.data = carry;
            carry=0;
          
          else:
            head1.data = carry%10;
            carry=int(carry/10);
          
          head1 = head1.next;
          auxiliary = obj2.head;
          obj2.head = obj2.head.next;  

          auxiliary = None;
        
        elif(head1 != None):
          current = head1;
          carry += head1.data;

          if(carry < 10):
            head1.data = carry;
            carry=0;
          
          else:
            head1.data = carry%10;
            ccarry=int(carry/10);
          
          head1 = head1.next;
        
        elif(obj2.head != None):
          current.next = obj2.head;
          current = obj2.head;

          carry += obj2.head.data;

          if(carry < 10):
            obj2.head.data = carry;
            carry=0;
          
          else:
            obj2.head.data = carry%10;
            carry=int(carry/10);
          
          obj2.head=obj2.head.next;
        

      
      while(carry != 0) :
        current.next = self.make_node(carry%10);
        carry=int(carry/10);
        current = current.next;
      
      self.reverse(); 
     
    

   

def main():

  #Create Object of class LinkedList
  obj1=LinkedList()
  obj2=LinkedList()
  #5112
  obj1.insert(5)
  obj1.insert(1)
  obj1.insert(1)
  obj1.insert(2)

  #99999
  obj2.insert(9)
  obj2.insert(9)
  obj2.insert(9)
  obj2.insert(9)
  obj2.insert(9)

  obj1.add_nodes(obj2)
  obj1.display()

if __name__ =="__main__":
  main()

Output

1 0 5 1 1 1
//C# program
//Add two numbers represented by linked list
using System;
public class Node
{
  public int data;
  public Node next;
}
public class LinkedList
{


  public Node head;
  //Class constructors
  LinkedList()
  {
    head=null;
  } 
  //insert  element
  public void insert(int value)
  {
    //Create  node
    Node node=new Node();
    node.data=value;
    node.next=null;
    if(head==null) head=node;
    else
    {
      Node temp=head;
      //find last node
      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=node;
    }

  }
  //Display all Linked List elements
  public void display()
  {
    if(head!=null)
    {
      Console.WriteLine("Linked List Element :");
      Node temp=head;
      while(temp!=null)
      {
        Console.Write("  "+temp.data);
        temp=temp.next;
      }
      Console.WriteLine();
    }else
    {
      Console.WriteLine("Empty Linked list"); 
    }
  }
  //reverse a single linked list
  public void reverse()
  {

    Node prev=null, temp=head;
    while(temp!=null)
    {
      //new head node
      head=temp;

      //visit to next node
      temp=temp.next;
      //change node link to pervious node
      head.next=prev;
      //get the reference of newly head node
      prev=head;
    }
  }

  //create new node of linked list
  public Node  make_node(int data)
  {
    Node auxiliary = null;

    auxiliary = new Node();


    auxiliary.next = null;
    auxiliary.data = data;


    return auxiliary;
  }

  public void add_nodes(LinkedList obj2)
  {

    if(obj2.head == null )
    {
      return;
    }
    else if( this.head == null ) 
    {

      this.head = obj2.head;
      obj2.head = null;
    }
    else
    {
      this.reverse();
      obj2.reverse();

      Node  auxiliary = null, head1=head, current=null;
      int carry = 0;
      while(head1 != null || obj2.head != null)
      {
        if(head1 != null && obj2.head != null)
        {
          current = head1;
          carry += head1.data + obj2.head.data;

          if(carry<10)
          {
            head1.data = carry;
            carry=0;
          }
          else
          {
            head1.data = carry%10;
            carry/=10;
          }
          head1 = head1.next;
          auxiliary = obj2.head;
          obj2.head = obj2.head.next;  

          auxiliary = null;
        }
        else if(head1 != null)
        {
          current = head1;
          carry += head1.data;

          if(carry < 10)
          {
            head1.data = carry;
            carry=0;
          }
          else
          {
            head1.data = carry%10;
            carry /= 10;
          }
          head1 = head1.next;
        }
        else if(obj2.head != null)
        {
          current.next = obj2.head;
          current = obj2.head;

          carry += obj2.head.data;

          if(carry < 10)
          {
            obj2.head.data = carry;
            carry=0;
          }
          else
          {
            obj2.head.data = carry%10;
            carry /= 10;
          }
          obj2.head=obj2.head.next;
        }

      }
      while(carry != 0)
      {
        current.next = make_node(carry%10);
        carry/=10;
        current = current.next;
      }
      this.reverse(); 

    }
  }
  public static void Main(String[] args) 
  {

    LinkedList obj1 = new LinkedList();
    LinkedList obj2 = new LinkedList();

    //5112
    obj1.insert(5);
    obj1.insert(1);
    obj1.insert(1);
    obj1.insert(2);

    //99999
    obj2.insert(9);
    obj2.insert(9);
    obj2.insert(9);
    obj2.insert(9);
    obj2.insert(9);

    obj1.add_nodes(obj2);
    obj1.display();
  }
}

Output

Linked List Element :
  1  0  5  1  1  1

<?php
//Php program 
//Add two numbers represented by linked list
class Node
{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data = $data;
    $this->next = NULL;
  }
}
class LinkedList
{

  public $head;
  function __construct()
  {
    $head=NULL;
  }
  /*
  * Append the Given data value at end of linked list
  * Fun : insert
  * Parm: data value
  *@return None
  */
  function insert($data)
  {
    $newNode=new Node($data); 

    if($this->head==NULL)
    {
      $this->head=$newNode;
    }
    else
    {
      $temp=$this->head;

      //find last node of linked list
      while($temp->next!=NULL)
      {
        $temp=$temp->next;
      }
      //add new node to last of linked list
      $temp->next=$newNode;
    }
  }
  //Display all inserted node in linked list
  function display()
  {
    if($this->head==NULL)
    {
      echo "Empty Linked List";
    }
    else
    {
      $temp=$this->head;
      echo "Linked List :";
      while($temp!=NULL)
      {
        //display node value
        echo "  ".$temp->data;
        $temp=$temp->next; //visit to next node
      }
    }   
  }
  //reverse a single linked list
  function reverse()
  {

    $prev=null;
    $temp=$this->head;
    while($temp!=null)
    {
      //new head node
      $this->head=$temp;
      
      //visit to next node
      
      $temp=$temp->next;
      //change node link to pervious node
      $this->head->next=$prev;
      //get the reference of newly head node
      $prev=$this->head;
    }
  }

  //create new node of linked list
  function make_node($data)
  {

    $auxiliary = new Node($data);

    return $auxiliary;
  }

  function add_nodes($obj2)
  {

    if($obj2->head == null )
    {
      return;
    }
    else if( $this->head == null ) 
    {

      $this->head = $obj2->head;
      $obj2->head = null;
    }
    else
    {
      $this->reverse();
      $obj2->reverse();

      $auxiliary = null;
      $head1=$this->head;
      $current=null;
      $carry = 0;
      while($head1 != null || $obj2->head != null)
      {
        if($head1 != null && $obj2->head != null)
        {
          $current = $head1;
          $carry += $head1->data + $obj2->head->data;

          if($carry<10)
          {
            $head1->data = $carry;
            $carry=0;
          }
          else
          {
            $head1->data = $carry%10;
            $carry=intval($carry/10);
          }
          $head1 = $head1->next;
          $auxiliary = $obj2->head;
          $obj2->head = $obj2->head->next;  

          $auxiliary = null;
        }
        else if($head1 != null)
        {
          $current = $head1;
          $carry += $head1->data;

          if($carry < 10)
          {
            $head1->data = $carry;
            $carry=0;
          }
          else
          {
            $head1->data = $carry%10;
            $carry=intval($carry/10);
          }
          $head1 = $head1->next;
        }
        else if($obj2->head != null)
        {
          $current->next = $obj2->head;
          $current = $obj2->head;

          $carry += $obj2->head->data;

          if($carry < 10)
          {
            $obj2->head->data =$carry;
            $carry=0;
          }
          else
          {
            $obj2->head->data = $carry%10;
            $carry /= 10;
          }
          $obj2->head=$obj2->head->next;
        }

      }
      while($carry != 0)
      {
        $current->next = $this->make_node($carry%10);
        $carry=intval($carry/10);
        $current = $current->next;
      }
      $this->reverse(); 

    }
  }
}
function main()
{
  //Make a object of LinkedList class
  $obj1= new LinkedList();
  $obj2= new LinkedList();
  
  //5112
  $obj1->insert(5);
  $obj1->insert(1);
  $obj1->insert(1);
  $obj1->insert(2);

  //99999
  $obj2->insert(9);
  $obj2->insert(9);
  $obj2->insert(9);
  $obj2->insert(9);
  $obj2->insert(9);

  $obj1->add_nodes($obj2);
  $obj1->display();
}
main();
?>

Output

Linked List :  1  0  5  1  1  1


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment




© 2021, kalkicode.com, All rights reserved