Add Two Numbers Ii

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 */

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        
        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        
        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        
        int sum = 0;
        ListNode* res = new ListNode(0);
        
        while (!s1.empty() || !s2.empty()) {
            if (!s1.empty()) { 
                sum += s1.top();
                s1.pop();
            }
            
            if (!s2.empty()) {
                sum += s2.top();
                s2.pop();
            }
            
            res->val = sum % 10;
            ListNode* head = new ListNode(sum / 10);
            head->next = res;
            res = head;
            sum /= 10;
        }
        
        return res->val == 0 ? res->next : res;
    }
};

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        // Convert linked lists to stacks
        Stack<int> stack1 = new Stack<int>();
        Stack<int> stack2 = new Stack<int>();
        
        while (l1 != null) {
            stack1.Push(l1.val);
            l1 = l1.next;
        }
        
        while (l2 != null) {
            stack2.Push(l2.val);
            l2 = l2.next;
        }
        
        int carry = 0;
        ListNode result = null;
        
        while (stack1.Count > 0 || stack2.Count > 0 || carry > 0) {
            int sum = carry;
            sum += stack1.Count > 0 ? stack1.Pop() : 0;
            sum += stack2.Count > 0 ? stack2.Pop() : 0;
            
            carry = sum / 10;
            sum %= 10;
            
            ListNode newNode = new ListNode(sum);
            newNode.next = result;
            result = newNode;
        }
        
        return result;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var addTwoNumbers = function(l1, l2) {
    let stack1 = [];
    let stack2 = [];
    
    while (l1) {
        stack1.push(l1.val);
        l1 = l1.next;
    }
    
    while (l2) {
        stack2.push(l2.val);
        l2 = l2.next;
    }
    
    let sum = 0;
    let result = new ListNode(0);
    
    while (stack1.length || stack2.length) {
        if (stack1.length) sum += stack1.pop();
        if (stack2.length) sum += stack2.pop();
        
        result.val = sum % 10;
        let head = new ListNode(Math.floor(sum / 10));
        head.next = result;
        result = head;
        sum = Math.floor(sum / 10);
    }
    
    return result.val === 0 ? result.next : result;
};

                                            
/*
Don't send code in this format
*/

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next? :ListNode){       
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let stack1: number[] = [];
    let stack2: number[] = [];
    
    while (l1) {
        stack1.push(l1.val);
        l1 = l1.next;
    }
    
    while (l2) {
        stack2.push(l2.val);
        l2 = l2.next;
    }
    
    let sum: number = 0;
    let resultList: ListNode | null = null;
    
    while (stack1.length > 0 || stack2.length > 0 || sum > 0) {
        if (stack1.length > 0) sum += stack1.pop()!;
        if (stack2.length > 0) sum += stack2.pop()!;
        
        let newNode: ListNode = new ListNode(sum % 10);
        newNode.next = resultList;
        resultList = newNode;
        
        sum = Math.floor(sum / 10);
    }
    
    return resultList;
}

                                            
class Solution {

    /**
     * Definition for a singly-linked list.
     * class ListNode {
     *     public $val = 0;
     *     public $next = null;
     *     function __construct($val = 0, $next = null) {
     *         $this->val = $val;
     *         $this->next = $next;
     *     }
     * }
     */

    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
        $stack1 = [];
        $stack2 = [];
        
        while ($l1 != null) {
            array_push($stack1, $l1->val);
            $l1 = $l1->next;
        }
        
        while ($l2 != null) {
            array_push($stack2, $l2->val);
            $l2 = $l2->next;
        }
        
        $carry = 0;
        $dummy = null;
        
        while (!empty($stack1) || !empty($stack2) || $carry > 0) {
            $num1 = !empty($stack1) ? array_pop($stack1) : 0;
            $num2 = !empty($stack2) ? array_pop($stack2) : 0;
            
            $sum = $num1 + $num2 + $carry;
            $carry = intdiv($sum, 10);
            
            $node = new ListNode($sum % 10);
            $node->next = $dummy;
            $dummy = $node;
        }
        
        return $dummy;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    stack1 := []*ListNode{}
    stack2 := []*ListNode{}

    for node := l1; node != nil; node = node.Next {
        stack1 = append(stack1, node)
    }
    for node := l2; node != nil; node = node.Next {
        stack2 = append(stack2, node)
    }

    var head *ListNode
    carry := 0
    for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
        sum := carry
        if len(stack1) > 0 {
            sum += stack1[len(stack1)-1].Val
            stack1 = stack1[:len(stack1)-1]
        }
        if len(stack2) > 0 {
            sum += stack2[len(stack2)-1].Val
            stack2 = stack2[:len(stack2)-1]
        }

        node := &ListNode{Val: sum % 10, Next: head}
        head = node
        carry = sum / 10
    }

    return head
}

                                            
class ListNode
    attr_accessor :val, :next
    def initialize(val = 0, _next = nil)
        @val = val
        @next = _next
    end
end

def add_two_numbers(l1, l2)
    stack1 = []
    stack2 = []
    
    while l1
        stack1.push(l1.val)
        l1 = l1.next
    end
    
    while l2
        stack2.push(l2.val)
        l2 = l2.next
    end
    
    carry = 0
    sum = nil
    
    while !stack1.empty? || !stack2.empty? || carry > 0
        val1 = stack1.empty? ? 0 : stack1.pop
        val2 = stack2.empty? ? 0 : stack2.pop
        total = val1 + val2 + carry
        carry = total / 10
        current = ListNode.new(total % 10)
        current.next = sum
        sum = current
    end
    
    sum
end

                                            
import scala.collection.mutable.Stack

/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 */

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        var stack1 = new Stack[Int]()
        var stack2 = new Stack[Int]()
        
        var temp1 = l1
        var temp2 = l2
        
        while(temp1 != null){
            stack1.push(temp1.x)
            temp1 = temp1.next
        }
        
        while(temp2 != null){
            stack2.push(temp2.x)
            temp2 = temp2.next
        }
        
        var carry = 0
        var result: ListNode = null
        
        while(!stack1.isEmpty || !stack2.isEmpty || carry != 0){
            var sum = carry
            if(!stack1.isEmpty) sum += stack1.pop()
            if(!stack2.isEmpty) sum += stack2.pop()
            
            val newNode = new ListNode(sum % 10)
            newNode.next = result
            result = newNode
            
            carry = sum / 10
        }
        
        result
    }
}

                                            
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>,
// }
impl Solution {
    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut stack1 = Vec::new();
        let mut stack2 = Vec::new();
        
        let mut head1 = &l1;
        let mut head2 = &l2;
        
        while let Some(node) = head1 {
            stack1.push(node.val);
            head1 = &node.next;
        }
        
        while let Some(node) = head2 {
            stack2.push(node.val);
            head2 = &node.next;
        }
        
        let mut carry = 0;
        let mut result = None;
        
        while !stack1.is_empty() || !stack2.is_empty() || carry != 0 {
            let mut sum = carry;
            if let Some(val) = stack1.pop() {
                sum += val;
            }
            if let Some(val) = stack2.pop() {
                sum += val;
            }
            carry = sum / 10;
            let node = Box::new(ListNode {
                val: sum % 10,
                next: result,
            });
            result = Some(node);
        }
        
        result
    }
}

To solve this coding challenge, you need to add two numbers represented by two linked lists where each node contains a single digit, and the most significant digit comes first. The output should also be in the form of a linked list where each node contains a single digit. Here’s an in-depth explanation followed by pseudocode with detailed comments:

Explanation

The key idea here is to add the two numbers digit by digit, considering the most significant digit first. Because you cannot easily add from the most significant to the least significant without knowing the complete structure of the numbers, one effective way is to use stacks to store the digits temporarily. Here’s the step-by-step process:

Use two stacks to hold the digits of the two input numbers (linked lists). Traverse each linked list and push its values to its respective stack. This way, the most significant digit is at the bottom of the stack, and the least significant is at the top.
Initialize a variable
sum

to zero and create a dummy node for the result linked list.
Use a loop to pop elements from both stacks (if available), add them along with any carry from the previous addition, and then handle the carry for the next significant digit.
Create nodes for the resulting linked list and insert them at the required positions.
Return the resultant linked list after handling any remaining carry.

Pseudocode

Initial pseudo-code can look like this in steps:

                                            
# Define a function to add two numbers represented by linked lists
Function addTwoNumbers(l1, l2):

# Initialize two empty stacks to hold the digits of the two linked lists
Initialize stack1 as an empty list
Initialize stack2 as an empty list

# Traverse the first linked list and push all the values onto stack1
While l1 is not None:
Push l1.val to stack1
Move to the next node in l1

# Traverse the second linked list and push all the values onto stack2
While l2 is not None:
Push l2.val to stack2
Move to the next node in l2

# Initialize the sum as 0
Initialize sum as 0

# Dummy node to start the result linked list
Initialize result as a new ListNode with value 0

# Loop until both stacks are empty
While stack1 is not empty or stack2 is not empty:

# If stack1 is not empty, pop the top element and add it to sum
If stack1 is not empty:
sum = sum + Pop(stack1)

# If stack2 is not empty, pop the top element and add it to sum
If stack2 is not empty:
sum = sum + Pop(stack2)

# Update the value of the current node in the result list
result.val = sum % 10

# Calculate the carry for the next iteration
Initialize head as a new ListNode with value as sum // 10

# Set the next of new head node to current result list
head.next = result

# Move result to the new head node
result = head

# Update sum for the next iteration
sum = sum // 10

# If the dummy node's value is 0, return the next node
If result.val == 0:
Return result.next

# Else, return the result node
Return result

# Function call example
# addTwoNumbers(l1, l2)

Detailed Steps in Pseudocode

Initialize two empty stacks called
stack1

and
stack2

.

Iterate through the first linked list (
l1

), pushing each node’s value onto
stack1

.
Iterate through the second linked list (
l2

), pushing each node’s value onto
stack2

.

Initialize a variable
sum

to zero. This will be used to hold the sum of the current digits plus any carryover.
Create a dummy node called
result

that will serve as the starting point of the resultant linked list.
Enter a loop that continues while either
stack1

or
stack2

contains elements.

Pop the top element from
stack1

(if it exists) and add it to
sum

.
Pop the top element from
stack2

(if it exists) and add it to
sum

.
Update the value of the current result node to be
sum % 10

– this represents the current digit of the resultant linked list.
Calculate the carry for the next digit addition using
sum // 10

.
Create a new node called
head

with the value of
sum // 10

.
Set
head.next

to the current result node.
Move
result

to the new head node.
Update
sum

to be
sum // 10

for the next iteration (carryover).

After the loop, check if the dummy node’s value is zero. If it is, return
result.next

(to skip the leading zero); otherwise, return
result

.

By following this structured approach and detailed pseudocode, you can implement a solution that adds two numbers represented by linked lists without reversing the input lists.