Question

Add two numbers represented by linked lists in java.
For Example:-
List1:- 1 2 3 4 5 9
List2:- 9 6 3
Output:- 1 2 4 4 2 2

Answer 1

See the following running example that adds two numbers which is represented by linked list.

Steps adding two numbers represented by linked list:-
1. Reverse both linked lists
2. Now add both linked list data from starts  to end.
3. New linked list get which is in reverse order of actual addition of both linked list
4. Reverse the added linked list and get your result.

package com.ds.linkedlist;

public class AddTwoNumbersOfLinkedList {

    Node head;
    public static void main(String[] args) {
        AddTwoNumbersOfLinkedList l1 = new AddTwoNumbersOfLinkedList();
        l1.insert(1);
        l1.insert(2);
        l1.insert(3);
        l1.insert(4);
        l1.insert(5);
        l1.insert(9);
        AddTwoNumbersOfLinkedList l2 = new AddTwoNumbersOfLinkedList();
        l2.insert(9);
        l2.insert(6);
        l2.insert(3);
       
        System.out.println("List1: ");
        l1.print();
       
        System.out.println("\nList2: ");
        l2.print();
       
        AddTwoNumbersOfLinkedList addTwoList = new AddTwoNumbersOfLinkedList();
        Node addedList = addTwoList.addNumbersOfLinkedList(l1.head, l2.head);
    }
   
    private Node addNumbersOfLinkedList(Node list1, Node list2) {
        list1 = reverseList(list1);
        list2 = reverseList(list2);
       
        System.out.println("\nAfter Reverse List1: ");
        this.head = list1;
        print();
        System.out.println("\nAfter Reverse List2: ");
        this.head = list2;
        print();
       
        Node added = addLinkedList(list1, list2);
        this.head = added;
        System.out.println("\nAdded Reverse List: ");
        print();
        this.head = reverseList(added);
        System.out.println("\nAdded List: ");
        print();
        return added;
    }

    private Node addLinkedList(Node list1, Node list2) {
        this.head = null;
        if(list1 == null && list2 == null)
            return null;
        else if(list1 == null)
            return list2;
        else if(list2 == null)
            return list1;
       
        int sum = 0, carry = 0, reminder = 0;
       
        //Both having same number of nodes
        while(list1 != null && list2 != null){
            sum = carry + list1.data + list2.data;
            carry = sum/10;
            if(carry == 0){
                insert(sum);
                reminder = 0;
            }else{
                reminder = sum%10;
                insert(reminder);
            }
            list1 = list1.next;
            list2 = list2.next;
        }
        //If list1 is bigger
        while(list1 != null){
            if(carry == 0){
                insert(list1.data);
            }else{
                sum = carry + list1.data;
                carry = sum/10;
                if(carry == 0){
                    insert(sum);
                    reminder = 0;
                }else{
                    reminder = sum%10;
                    insert(reminder);
                }
            }
            list1 = list1.next;
        }
       
        //If list2 is bigger
        while(list2 != null){
            if(carry == 0){
                insert(list2.data);
            }else{
                sum = carry + list2.data;
                carry = sum/10;
                if(carry == 0){
                    insert(sum);
                    reminder = 0;
                }else{
                    reminder = sum%10;
                    insert(reminder);
                }
            }
            list2 = list2.next;
        }
        if(carry > 0){
            insert(carry);
        }
        return this.head;
    }

    private Node reverseList(Node list) {
        Node prev = null;
        while(list.next != null){
            Node next = list.next;
            list.next = prev;
            prev = list;
            list = next;
        }
       
        list.next = prev;
       
        return list;
    }

    private class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }
   
    public void insert(int data){
        Node newNode = new Node(data);
        if(head == null){
            head = newNode;
        }else{
            Node curr = head;
            while(curr.next != null){
                curr = curr.next;
            }
            curr.next = newNode;
        }
    }
   
    public void print(){
        if(head==null)
            return;
        Node curr = head;
        while(curr != null){
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
    }

}



Output:-
List1:
1 2 3 4 5 9
List2:
9 6 3
After Reverse List1:
9 5 4 3 2 1
After Reverse List2:
3 6 9
Added Reverse List:
2 2 4 4 2 1
Added List:
1 2 4 4 2 2

Answer 2

Following Methods to add two numbers which is represented by linked list.

Steps to add two numbers represented by linked list:-
1. Convert linked list to number
2. Add both numbers which you have converted linked list to number
3. Now convert number to linked list and get result.

//Add Two Numbers of linked list by converting linked list to number and number to linked list
private Node addLinkedListToConvert(Node list1, Node list2) {
    int firstNum = listToNumber(list1);
    int secondNum = listToNumber(list2);
    int sum = firstNum + secondNum;
    Node addedList = numerToLinkedList(sum);
    return addedList;
}

//Convert linked list to number
private int listToNumber(Node list) {
    if(list == null)
        return 0;
    int num = 0;
    while(list != null){
        if(num == 0){
            num = list.data;
        }else{
            num = num * 10 + list.data;
        }
        list = list.next;
    }
    return num;
}

//Convert number to linked list
private Node numerToLinkedList(int sum) {
    Node addedLinkedList = null;
    int num = sum;
    while(num > 0){
        int reminder = num%10;
        addedLinkedList = append(reminder, addedLinkedList);
        num = num/10;
    }
    return addedLinkedList;
}

//Append linked list
private Node append(int num, Node addedLinkedList) {
    Node node = new Node(num);
    if(addedLinkedList == null){
        addedLinkedList = node;
    }else{
        node.next = addedLinkedList;
        addedLinkedList = node;
    }
    return addedLinkedList;
}


Output:-
List1:
1 2 3 4 5
List2:
9 6 3
Added List:
1 3 3 0 8