Question

Add 1 to a number represented in linked list.
List: - [1, 9, 9, 9]
Result:- [2, 0, 0, 0]

Answer 1

Following example to add any number in given linked list. See the algorithm which add a number in linked list.
Step1:- First of all convert the given linked list to number by using getNumFromLinkedList() method.
Step2:- And add number like 1 in it.
Step3:- Now, get the sum of actual number. Then convert number to linked list by using getNodeListFromSum() method. Finally, you get the result.

package com.ds.linkedlist;

public class Add1NumberInLinkedList {

Node head;
   
    /**
     * @param args
     */
    public static void main(String[] args) {
        Add1NumberInLinkedList list = new Add1NumberInLinkedList();
        list.insert(1);
        list.insert(9);
        list.insert(9);
        list.insert(9);
        System.out.println("Original List: - ");
        list.print();
       
        Add1NumberInLinkedList addedList = new Add1NumberInLinkedList();
        Node added = addedList.add1InLinkedList(list.head, 1);
        System.out.println("\nAfter addition List: - ");
        addedList.head = added;
        addedList.print();
    }

    /**
     * This program converts linked list to number, get sum of given number with list
     * and again converts number to linked list.
     *
     * @param list
     * @param num
     * @return
     */
    private Node add1InLinkedList(Node list, int num) {
        Node current = list;
        int listToNum = getNumFromLinkedList(current);
        int sum = listToNum + num;
        Node node = getNodeListFromSum(sum);
        return node;
    }
   
    private Node getNodeListFromSum(int sum) {
        Node finalNode = null;
        while(sum != 0){
            int rem = sum % 10;
            sum = sum / 10;
            finalNode = addFirst(finalNode, rem);
        }
        return finalNode;
    }
   
    private Node addFirst(Node node, int num){
        Node newNode = new Node(num);
        newNode.next = node;
        node = newNode;
        return node;
    }
   
    private int getNumFromLinkedList(Node node) {
        Node current = node;
        int num = 0, count = 0;
        while(current != null){
            if(count == 0)
                num = current.data;
            else
                num = num * 10 + current.data;
            current = current.next;
            count++;
        }
        return num;
    }

    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:-
Original List: -
1 9 9 9
After addition List: -
2 0 0 0

Answer 2

See the following running example to add a number in given linked list.

Algorithm for adding a number in given linked list:-
Step1:- Reverse the given linked list.
Step2:- Add given number like : 1.
Step3:- Again reverse the modified linked list and return modified list.

package com.ds.linkedlist;

public class Add1NumberInLinkedList {

Node head;
   
    /**
     * @param args
     */
    public static void main(String[] args) {
        Add1NumberInLinkedList list = new Add1NumberInLinkedList();
        list.insert(1);
        list.insert(9);
        list.insert(9);
        list.insert(9);
        System.out.println("Original List: - ");
        list.print();
       
        Add1NumberInLinkedList addedList = new Add1NumberInLinkedList();
        Node added = addedList.add1InLinkedListUsingReverse(list.head, 1);
        System.out.println("\nAfter addition List: - ");
        addedList.head = added;
        addedList.print();
    }

    /**
     * Reverse given linked list. 1-> 9-> 9 -> 9 to 9-> 9 -> 9 ->1
     * Add given number like : 1
     * Reverse modified linked list and return after modification
     *
     * @param list
     * @param num
     * @return
     */
    private Node add1InLinkedListUsingReverse(Node list, int num) {
        Node current = list;
        //Reverse given linked list. 1-> 9-> 9 -> 9 to 9-> 9 -> 9 ->1
        Node prev = getReverseList(current);
        //Add given number like : 1
        Node addedList = addNumInLinkedList(num, prev);
        //Reverse modified linked list and return after modification
        return getReverseList(addedList);
    }

    private Node addNumInLinkedList(int num, Node prev) {
        Node current;
        current = prev;
        int carry = 0;
        int count = 0;
        int sum = 0;
        while(current != null){
            if(count == 0){
                sum = current.data + num ;
            }else{
                sum = current.data + carry ;
            }
           
            if(sum > 9){
                carry = 1;
                sum = sum%10;
            }else{
                carry = 0;
            }
            current.data = sum;
            current = current.next;
        }
        return prev;
    }

    private Node getReverseList(Node current) {
        Node prev = null;
        while(current != null){
            Node tempNext = current.next;
            current.next = prev;
            prev = current;
            current = tempNext;
        }
        return prev;
    }

    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:-
Original List: -
1 9 9 9
After addition List: -
2 0 0 0