Software Development

Add two numbers represented by Linked List


import java.util.*;

 

class GFG {

 

    static class Node {

        int data;

        Node next;

    };

 

    

    static Node addition(Node temp1, Node temp2, int size1,

                         int size2)

    {

        

        Node newNode = new Node();

 

        

        if (temp1 != null && temp2 != null

            && temp1.next == null && temp2.next == null) {

            

            

            newNode.data = (temp1.data + temp2.data);

 

            

            newNode.next = null;

 

            

            return newNode;

        }

 

        

        

        Node returnedNode = new Node();

 

        

        

        if ((temp1 != null && temp2 != null)

            && size2 == size1) {

            

            

            returnedNode = addition(temp1.next, temp2.next,

                                    size1 - 1, size2 - 1);

 

            

            newNode.data = (temp1.data + temp2.data)

                           + ((returnedNode.data) / 10);

        }

        

        else if (temp1 != null && temp2 != null) {

            

            

            returnedNode = addition(temp1, temp2.next,

                                    size1, size2 - 1);

 

            

            newNode.data

                = (temp2.data) + ((returnedNode.data) / 10);

        }

 

        

        

        returnedNode.data = (returnedNode.data) % 10;

 

        

        newNode.next = returnedNode;

 

        

        return newNode;

    }

 

    

    

    static Node addTwoLists(Node head1, Node head2)

    {

        Node temp1, temp2, ans = null;

 

        temp1 = head1;

        temp2 = head2;

 

        int size1 = 0, size2 = 0;

 

        

        while (temp1 != null) {

            temp1 = temp1.next;

            size1++;

        }

        

        while (temp2 != null) {

            temp2 = temp2.next;

            size2++;

        }

 

        Node returnedNode = new Node();

 

        

        if (size2 > size1) {

            returnedNode

                = addition(head1, head2, size1, size2);

        }

        else {

            returnedNode

                = addition(head2, head1, size2, size1);

        }

 

        

        if (returnedNode.data >= 10) {

            ans = new Node();

            ans.data = (returnedNode.data) / 10;

            returnedNode.data = returnedNode.data % 10;

            ans.next = returnedNode;

        }

        else

            ans = returnedNode;

 

        

        

        return ans;

    }

 

    static void Display(Node head)

    {

        if (head == null) {

            return;

        }

        while (head.next != null) {

            System.out.print(head.data + " -> ");

            head = head.next;

        }

        System.out.print(head.data + "\n");

    }

    

    

    static Node push(Node head_ref, int d)

    {

        Node new_node = new Node();

        new_node.data = d;

        new_node.next = null;

        if (head_ref == null) {

            new_node.next = head_ref;

            head_ref = new_node;

            return head_ref;

        }

        Node last = head_ref;

        while (last.next != null && last != null) {

            last = last.next;

        }

        last.next = new_node;

        return head_ref;

    }

    

    public static void main(String[] args)

    {

        

        Node first = null;

        Node second = null;

        Node sum = null;

        first = push(first, 7);

        first = push(first, 5);

        first = push(first, 9);

        first = push(first, 4);

        first = push(first, 6);

        second = push(second, 8);

        second = push(second, 4);

        System.out.print("First List : ");

        Display(first);

        System.out.print("Second List : ");

        Display(second);

        sum = addTwoLists(first, second);

        System.out.print("Sum List : ");

        Display(sum);

    }

}