DEV Community

Cover image for Add 1 to a number represented as linked list.
Tejas Patil
Tejas Patil

Posted on

Add 1 to a number represented as linked list.

The given problem is of level easy but when you are a beginners it is very hard to solve the problems without reference. So to increase our logical thinking we have to solve at least one problem a day. The problem which is given below is solved by me today.

Problem:- Add 1 to a number represented as linked list.

A number N is represented in Linked List such that each digit corresponds to a node in linked list. You need to add 1 to it.

Example 1:

Input:
LinkedList: 4->5->6
**Output:
457
Example 2:

Input:
LinkedList: 1->2->3
Output: 124
Your Task:
Your task is to complete the function addOne() which takes the head of the linked list as the only argument and returns the head of the modified linked list. The driver code prints the number.
Note: The head represents the left-most digit of the number.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 10100

Solution.java

class Solution
{
    public static Node addOne(Node head) 
    {  
      Node pre = null;
       while(head!=null){
         Node temp1 = head.next;
         head.next = pre;
         pre = head;
         head= temp1;
     }
         Node temp = pre;
         Node prev = null;

     while(temp!=null){

         if(temp.data +1 >=10){
             temp.data = 0;
             prev  = temp;
             temp=temp.next;
         }
         else{
             temp.data = temp.data +1;
             break;
         }
     }

     if(temp==null){
         Node n = new Node(1);
         prev.next = n;
     }
     Node ans = null;

          while(pre!=null){
         Node temp1 = pre.next;
         pre.next = ans;
         ans = pre;
         pre= temp1;
     }

     return ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

Github Profile:- https://github.com/tejas910

Top comments (0)