LL 14 - Add 1 to a Linked List Number

Problem

You are given a linked list where each element in the list is a node and have an integer data. You need to add 1 to the number formed by concatinating all the list node numbers together and return the head of the modified linked list. (link)

Note: The head represents the first element of the given array.

Examples :

Input: LinkedList: 4->5->6
Output: 457

Explanation: 4->5->6 represents 456 and when 1 is added it becomes 457.
--------------------------------------------------------------------------
Input: LinkedList: 1->2->3
Output: 124

Explanation:  1->2->3 represents 123 and when 1 is added it becomes 124.

Solution

Brute Force Approach

We need to add one to the end node of the linked list. If adding one to the last node causes it to exceed 10, that node will be marked as 0, and a carry of 1 will be added to the previous node. To handle this carry operation, we reverse the linked list and perform the addition. After completing the addition, we reverse the list again and return it. If there is still a carry of 1 left after processing all the nodes, we need to add a new node to the head and return the new head.

Time - O(n)

Space - O(1)

class Solution {
    public Node reverse(Node head){
        if(head == null || head.next == null) return head;

        Node temp = head;
        Node prev = null;

        while(temp!=null){

            Node next = temp.next;
            temp.next = prev;
            prev = temp;
            temp = next;
        }

        return prev;
    }
    public Node addOne(Node head) {
        Node reversedHead = reverse(head);

        Node temp = reversedHead;
        int carry = 1;

        while(temp!=null){
            int val = temp.data + carry;
            if(val==10){
                temp.data = 0;
                carry = 1;
            }
            else{
                temp.data = val;
                carry=0;
                break;
            }
            temp = temp.next;
        }

        head = reverse(reversedHead);
        if(carry==1){
            Node newHead = new Node(1);
            newHead.next = head;
            return newHead;
        }
        return head;
    }
}

Optimal Solution (Recurrsive)

Get the carry value from the next node and add it to the current node. Set the carry to 0 if the sum is less than 10; otherwise, return 1.

Time - O(n)

Space - O(n)

class Solution {
    public int helper(Node node){
        if(node == null) return 1;

        node.data = node.data + helper(node.next);
        if(node.data<10) return 0;

        node.data = 0;
        return 1;
    }

    public Node addOne(Node head) {
        int carry = helper(head);
        if(carry == 1){
            Node newNode = new Node(1);
            newNode.next = head;
            head = newNode;
        }
        return head;
    }
}