Add two numbers represented by linked lists in java

Add two numbers represented by linked lists in java

Given two numbers represented by two linked lists of size N and M. The task is to return a sum list.
The sum list is a linked list representation of the addition of two input numbers from the last.

Input

The first line inputs N and M ,the size of two linked lists.
The second line inputs the value of N nodes of 1st linked list.
The third line inputs the value of M nodes of 2nd linked list.\

Constraints:

1 <= N, M <= 5000

Output

Print the sum list in new line.

Example

Input:

2 3
4 5 
3 4 5

Output:

3 9 0

Explaination:

For the given two linked
list (4 5) and (3 4 5), after adding
the two linked list resultant linked
list will be (3 9 0).

Solution of Add two numbers represented by linked lists in java:–

import java.util.*;
import java.lang.*;
import java.io.*;

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
public class Main
{
  static void printlist(Node head)
    {
        Node currNode=head;
        while(currNode!=null)
        {
            System.out.print(currNode.data+" ");
            currNode=currNode.next;
        }
    }
  static Node insertAtHead(Node head, int data)
    {
        Node NewNode=new Node(data);
        NewNode.next=head;
        return NewNode;
    }
   static Node addnumbers(Node head1, Node head2)
  {
    Node dummy=new Node(0);
    Node curr=dummy;
    Node c1=head1;
    Node c2=head2;
    
    int sum=0,carry=0;
    while(c1!=null || c2!=null)
      {
        int x=(c1==null?0:c1.data);
        int y=(c2==null?0:c2.data);
        sum=x+y+carry;
        carry=sum/10;
        curr.next=new Node(sum%10);
        curr=curr.next;
        
        if(c1!=null)
          c1=c1.next;
        
        if(c2!=null)
          c2=c2.next;
      }
    if(carry>0)
    {
      curr.next=new Node(carry);
    }
    return dummy.next;
  }
  static Node reverse(Node head)
  {
    Node curr=head;
    Node prev=null;
    while(curr!=null)
      {
        Node temp=curr.next;
        curr.next=prev;
        prev=curr;
        curr=temp;
      }
    return prev;
  }
	public static void main (String[] args) throws java.lang.Exception
	{
		//your code here
        Scanner sc=new Scanner(System.in);
        Node head1=null;
        Node head2=null;
        int n=sc.nextInt();
        int m=sc.nextInt();
        for(int i=0;i<n;i++)
        {
            int data=sc.nextInt();
            head1=insertAtHead(head1,data);
        }
      for(int i=0;i<m;i++)
        {
            int data=sc.nextInt();
            head2=insertAtHead(head2,data);
        }
        
        Node head=addnumbers(head1,head2);
        Node reversehead=reverse(head);
        printlist(reversehead);
	}
}

Add a Comment

Your email address will not be published. Required fields are marked *