Plus One Linked List

Tags: , , ,

Given a number represented by a linked list, add 1 to that number and return a new linked list. For example, if the number is 2345, then it is represented as linked as shown below.

plus one linked list

When we add one to 2345 represented by the linked list, the resulting linked list looks as follows.

add 1 to linked list

Thought process

First of all, think if there is only one node in the linked list, that means the linked list represents a single-digit number. What will do? We will add 1 to the node.val and return a new node with the sum. This is our smallest case, however, there is a catch here as well. What if the single-digit number is 9. In that case, the sum is 10 and since every node contains only a single digit of the number, we can store 0 in the new node. What happens to 1? We can treat that 1 as a carry.
Now, there are no digits present to add carry to (remember we had only one node linked list), we will create a new node and put carry in that and then linked the carry node to the previous node with 0.

add one to linked list

This is a very important case which we learned here. When you have processed all the nodes of the linked list, if the carry remains, create a new node and attach it to the head of the list. Most of the students make a mistake in this case.

How about when there is more than one node in the linked list? In that case, 1 is added to the node in the end and carry is propagated, if any, backward till head. Next question, how can you process the last node of the linked list and move backward? Well, remember how we print a linked list in the reverse order. We go deep in the linked list till the last node and use recursion unfolding to come backward. We can use the same concept. Go to the last node recursively, maintain a carry and move backward till the head. Once, you have processed head node, check if carry is non zero, if it is, creates a new node and attach it at front.

plus one linked list

plus 1 in linked list

Show me the implementation

package AlgorithmsAndMe;

import java.util.List;

public class PlusOne {
    int carry = 0;


    public ListNode addOneToLinkedList(ListNode head){
        ListNode newList = addOneToLinkedListUtil(head, 1);

        if(carry > 0){
            ListNode newNode = new ListNode(carry);
            newNode.setNext(newList);
            return newNode;
        }
        return newList;
    }

    public ListNode addOneToLinkedListUtil(ListNode head, int val){

        if(head == null) return null;

        if(head.getNext() == null){
            return createNode(head, val);
        }

        ListNode returnedNode = 
             addOneToLinkedListUtil(head.getNext(), val);

        ListNode newNode = createNode(head, carry);
        newNode.setNext(returnedNode);

        return newNode;
    }

    private ListNode createNode(ListNode node, int val){
        int newVal = node.getValue() + val % 10;
        carry = (node.getValue() + val) / 10;

        return new ListNode(newVal);
    }
}

The complexity of the code is O(n), we will be processing each node at least once. The tricky part is space complexity, as recursion takes implicit stack memory, the space complexity is also O(n).
This code creates a new node, what if we new list does not have to be created and we have to return the same list back. The below code implements the PlustOne such that it returns the same list back.

package AlgorithmsAndMe;

import java.util.List;

public class PlusOne {

    public ListNode addOneToLinkedList2(ListNode head){
        int c = addOneToLinkedListUtil2(head);

        if(carry > 0){
            ListNode newNode = new ListNode(carry);
            newNode.setNext(head);
            return newNode;
        }
        return head;
    }

    public int addOneToLinkedListUtil2(ListNode head){

        if(head == null) return 1;
        int sum = head.getValue() 
                      + addOneToLinkedListUtil2(head.getNext());
        head.setVal(sum % 10);

        return sum / 10;
    }
}

In the next post, we will look at how to add two numbers represented by two linked lists.

If you are preparing for interview and looking for personalized coaching, please reach out to us on [email protected] or book a free session with us.