Untitled

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode addOne(ListNode head) {
        // Add one using backtracking
        int carry = addOneRecursive(head);
        
        // If there's a carry left, create a new node
        if (carry > 0) {
            ListNode newHead = new ListNode(carry);
            newHead.next = head;
            return newHead;
        }
        
        return head;
    }
    
    private int addOneRecursive(ListNode node) {
        // Base case: end of the list
        if (node == null) {
            return 1; // Initial carry is 1
        }
        
        // Recursively call for the next node
        int carry = addOneRecursive(node.next);
        
        // Add the carry to the current node's value
        int sum = node.val + carry;
        node.val = sum % 10; // Update the current node's value
        return sum / 10;     // Return the carry
    }
}