Head Recursion

In this problem a head-recursive solution is needed. Start the solution by calling the function recursively until the end of the list is reached. On the way back process the results, until you get to the head of the list (by checking the parent node being equal to null). Code is down below, cheers, ACC.

Double a Number Represented as a Linked List - LeetCode

2816. Double a Number Represented as a Linked List

Medium

You are given the head of a non-empty linked list representing a non-negative integer without leading zeroes.

Return the head of the linked list after doubling it.

 

Example 1:

Input: head = [1,8,9]
Output: [3,7,8]
Explanation: The figure above corresponds to the given linked list which represents the number 189. Hence, the returned linked list represents the number 189 * 2 = 378.

Example 2:

Input: head = [9,9,9]
Output: [1,9,9,8]
Explanation: The figure above corresponds to the given linked list which represents the number 999. Hence, the returned linked list reprersents the number 999 * 2 = 1998. 

 

Constraints:

• The number of nodes in the list is in the range [1, 104]
• 0 <= Node.val <= 9
• The input is generated such that the list represents a number that does not have leading zeros, except the number 0 itself.

public ListNode DoubleIt(ListNode head)
{
    int carryOver = 0;
    ListNode retVal = null;

    DoubleIt(null, head, ref carryOver, ref retVal);

    return retVal;
}

private void DoubleIt(ListNode parentNode,
                        ListNode currentNode,
                        ref int carryOver,
                        ref ListNode retVal)
{
    if (currentNode == null) return;

    DoubleIt(currentNode, currentNode.next, ref carryOver, ref retVal);

    int val = 2 * currentNode.val + carryOver;
    currentNode.val = val % 10;
    carryOver = val / 10;

    if (parentNode == null)
    {
        if (carryOver > 0)
        {
            ListNode head = new ListNode(carryOver);
            head.next = currentNode;
            retVal = head;
        }
        else
        {
            retVal = currentNode;
        }
    }
}