Sum of all distinct nodes in a linked list

Given a linked list, Find the sum of all distinct nodes of this linked list. That is simple problem but comparing one node to other and finding unique nodes this process are tack O(n^2) time.

Suppose we are inserted the following (4, 5, 2, 3, 5, 7) node in a sequence.

Sum of distinct nodes

Here given code implementation process.

//C Program 
//Sum of all distinct nodes in linked list
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
  int data;
  struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
//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;
    }
  }
}
//Return the sum of distinct element
int distinct_sum(struct Node*head){

  int result=0,flag=0;
  struct Node*temp=head,*checker=NULL;
  while(temp!=NULL)
  {
      //reset checker pointer
      checker=head;
      //flag are used to check exist element is repeated or not
      flag=1;
      while(checker!=NULL)
      {
        if(checker!=temp && checker->data==temp->data)
        {
          //when repeated element are found
          flag=0;
          break; 
        }
        checker=checker->next;
      }
      if(flag==1)
      {
          //when unique element
        result+=temp->data;
      }
      temp=temp->next;
    }

  
  return result;

}
//Display element of Node
void display(struct Node*temp){

  if(temp==NULL){
    printf("Empty linked list");
  }else{
    printf("Linked List : ");
    while(temp!=NULL){
      printf("%d  ",temp->data);
      temp=temp->next;
    }
  }

}
int main(){
  //create node pointer
  struct Node*head=NULL;
  //insert element of linked list

  insert(&head,4);
  insert(&head,5);
  insert(&head,2);
  insert(&head,3);
  insert(&head,5);
  insert(&head,7);
  //display all node
  display(head);
  printf("\nDistinct Sum: %d\n",distinct_sum(head));
}

Output

Linked List : 4  5  2  3  5  7  
Distinct Sum: 16
//C++ Program 
//Sum of all distinct nodes in linked list
#include<iostream>
using namespace std;

//create structure
struct Node{
  int data;
  struct Node*next;
};
class LinkedList{
  Node*head;//head node
  public:
    LinkedList();
    void insert(int);
    void display();
    int distinct_sum();
};
LinkedList::LinkedList(){
  head=NULL;
}
//insert node at end of linked list
void LinkedList::insert(int value){
    //Create dynamic node
  struct 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;
    }
  }
}
//Return the sum of distinct element
int LinkedList::distinct_sum(){

  int result=0,flag=0;
  struct Node*temp=head,*checker=NULL;
  while(temp!=NULL)
  {
      //reset checker pointer
      checker=head;
      //flag are used to check exist element is repeated or not
      flag=1;
      while(checker!=NULL)
      {
        if(checker!=temp && checker->data==temp->data)
        {
          //when repeated element are found
          flag=0;
          break; 
        }
        checker=checker->next;
      }
      if(flag==1)
      {
          //when unique element
        result+=temp->data;
      }
      temp=temp->next;
    }

  
  return result;

}
//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;
    }
  }

}
int main(){
 
  //create object
  LinkedList obj;
  //insert element of linked list
  obj.insert(4);
  obj.insert(5);
  obj.insert(2);
  obj.insert(3);
  obj.insert(5);
  obj.insert(7);
  //display all node
  obj.display();
  cout<<"\nDistinct Node sum : "<<obj.distinct_sum()<<endl;
}

Output

Linked List : 4 5 2 3 5 7 
Distinct Node sum : 16
//Java Program
//Sum of all distinct nodes in linked list
class Node {
  public int data;
  public Node next;
  public Node(int value) {
    data = value;
    next = null;
  }
}

public class LinkedList {

  public Node head;
  //Class constructors
  LinkedList() {
    head = null;
  }
  //insert element
  public void insert(int value) {
    //Create  node
    Node node = new Node(value);

    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;
      }
    } else {
      System.out.println("Empty Linked list");
    }
  }
  //return the sum of distinct element
  public int distinctSum() {

    int result = 0, flag = 0;
    Node temp = head, checker = null;
    while (temp != null) {
      //reset checker pointer
      checker = head;
      //flag are used to check exist element is repeated or not
      flag = 1;
      while (checker != null) {
        if (checker != temp && checker.data == temp.data) {
          //when repeated element are found
          flag = 0;
          break;
        }
        checker = checker.next;
      }
      if (flag == 1) {
        //when unique element
        result += temp.data;
      }
      temp = temp.next;
    }


    return result;

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

    LinkedList obj = new LinkedList();
    //insert linked list element
    obj.insert(4);
    obj.insert(5);
    obj.insert(2);
    obj.insert(3);
    obj.insert(5);
    obj.insert(7);
    //display all node
    obj.display();
    System.out.print("\nDistinct Node sum : " + obj.distinctSum());

  }
}

Output

Linked List Element :  4  5  2  3  5  7
Distinct Node sum : 16
#Python 
#Sum of all distinct nodes in linked list
class Node:
    def __init__(self,data):
        self.data=data
        self.next=None

#Create Class Linked    
class Linked:
    def __init__(self):
        #Assign default value
        self.head=None

    #insert new node to linked list  
    def insert(self,data):
        node=Node(data)
        node.next=None
        if self.head==None:
            self.head=node
        else:
            temp=self.head
            while temp.next!=None:
                temp=temp.next
            #add node    
            temp.next=node

    def display(self):
        temp=self.head
        print("Linked List Elements : ")

        while(temp!=None):
          print(temp.data,end=" ")
          temp=temp.next
        print("\n")

    def distinctSum(self):

        result=0
        flag=0
        temp=self.head
        checker=None
        while(temp!=None):

            #reset checker pointer
            checker=self.head;
            #flag are used to check exist element is repeated or not
            flag=1;
            while(checker!=None):

              if(checker!=temp and checker.data==temp.data):
                #when repeated element are found
                flag=0;
                break; 
              
              checker=checker.next;
            
            if(flag==1):
                #when unique element
                result+=temp.data;
            
            temp=temp.next;
          

    
        return result;

  
def main():
    #Create Object of class Linked
    obj=Linked()
     #insert linked list element
    obj.insert(4);
    obj.insert(5);
    obj.insert(2);
    obj.insert(3);
    obj.insert(5);
    obj.insert(7);
    #display all node
    obj.display();
    print("Distinct Node sum : ",obj.distinctSum());

      
if __name__=="__main__":
    main()

Output

Linked List Elements : 
4 5 2 3 5 7 

Distinct Node sum :  16
//C# Program
//Sum of all distinct nodes in linked list
using System;
//node class
public class Node{
   public  int data;
   public  Node next;
}
class Program
{
    Node head;
    public Program(){
        head=null;
    }
    //insert node of linked list
    public void insert(int data){
        Node newNode=new Node();
        newNode.data=data;
        newNode.next=null;
        if(head==null) head=newNode;
        else{
            Node temp=head;
            //get last node
            while(temp.next!=null){
                temp=temp.next;
            }
            //add new node
            temp.next=newNode;
        }
    }
    //display linked list nodes value
    public void display(){
        if(head==null){
            Console.Write("Empty List");
        }else{
            Node temp=head;
            while(temp!=null){
                Console.Write("  {0}",temp.data);
                temp=temp.next;
            }
            
        }
    }
     //return the sum of distinct element
    public int distinctSum(){

      int result=0,flag=0;
      Node temp=head, checker=null;
      while(temp!=null)
      {
          //reset checker pointer
          checker=head;
          //flag are used to check exist element is repeated or not
          flag=1;
          while(checker!=null)
          {
            if(checker!=temp && checker.data==temp.data)
            {
              //when repeated element are found
              flag=0;
              break; 
            }
            checker=checker.next;
          }
          if(flag==1)
          {
              //when unique element
            result+=temp.data;
          }
          temp=temp.next;
        }

      
      return result;

    }
    static void Main()
    {
        Program obj=new Program();
       //insert linked list element
        obj.insert(4);
        obj.insert(5);
        obj.insert(2);
        obj.insert(3);
        obj.insert(5);
        obj.insert(7);
        //display all node
        obj.display();
        Console.Write("\nDistinct Node sum : "+obj.distinctSum());

    }
}

Output

4 5 2 3 5 7
Distinct Node sum : 16
<?php
//Php program 
//Sum of all distinct nodes in linked list
class Node
{
    public $data;
    public $next;
    function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }
}
class LinkedList{

    private $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
            }
        }   
    }
     //Return the sum of distinct element
    function distinct_sum(){

      $result=0;
      $flag=0;
      $temp=$this->head;
      $checker=NULL;
      while($temp!=NULL)
      {
          //reset checker pointer
          $checker=$this->head;
          //flag are used to check exist element is repeated or not
          $flag=1;
          while($checker!=NULL)
          {
            if($checker!=$temp && $checker->data==$temp->data)
            {
              //when repeated element are found
              $flag=0;
              break; 
            }
            $checker=$checker->next;
          }
          if($flag==1)
          {
              //when unique element
            $result+=$temp->data;
          }
          $temp=$temp->next;
        }

      
      return $result;

    }
}
function main(){
  //Make a object of LinkedList class
  $obj= new LinkedList();

  /*
  *Insert following nodes in linked list
  */
  $obj->insert(4);
  $obj->insert(5);
  $obj->insert(2);
  $obj->insert(3);
  $obj->insert(5);
  $obj->insert(7);
  $obj->display();

  echo "<br>Distinct Sum: ".$obj->distinct_sum();
}
main();
?>

Output

Linked List : 4 5 2 3 5 7
Distinct Sum: 16

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