Add Two Numbers

                                            
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    curr, carry = dummy, 0

    while l1 or l2 or carry:
        val = carry
        if l1:
            val += l1.val
            l1 = l1.next
        if l2:
            val += l2.val
            l2 = l2.next
        carry, val = divmod(val, 10)
        curr.next = ListNode(val)
        curr = curr.next
        
    return dummy.next

                                            
class ListNode{
    constructor(val, next = null){
        this.val = val;
        this.next = next;
    }
}
  

const addTwoNumbers = (l1, l2) =>{
    const addLists = (num1, num2, carry = 0) => {
        if (!num1 && !num2 && !carry) return null;
        const newVal = (num1?.val || 0) + (num2?.val || 0) + carry;
        const nextNode = addLists(num1?.next, num2?.next, Math.floor(newVal / 10));
        return new ListNode(newVal % 10, nextNode);
    }
    return addLists(l1, l2);
};

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

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
        int carry = 0;
        while(l1!=null || l2!=null || carry==1){
            int num = carry;
            if(l1!=null){
                num+=l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                num+=l2.val;
                l2 = l2.next;
            }
            carry = num / 10;
            curr.next = new ListNode(num % 10);;
            curr = curr.next;
        }
        return dummy.next;
    }
}

                                            
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	carry, dummy := 0, new(ListNode)
	for node := dummy; l1 != nil || l2 != nil || carry > 0; node = node.Next {
		if l1 != nil {
			carry += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			carry += l2.Val
			l2 = l2.Next
		}
		node.Next = &ListNode{carry % 10, nil}
		carry /= 10
	}
	return dummy.Next
}

                                            
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;
        int carry = 0;
        
        while (l1 != nullptr || l2 != nullptr || carry) {
            int sum = carry;
            if (l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != nullptr) {
                sum += l2->val;
                l2 = l2->next;
            }
            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
        }
        
        return dummy->next;
    }
};

                                            
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *dummy = (struct ListNode*) malloc(sizeof(struct ListNode));
    struct ListNode *current = dummy;
    int carry = 0;
    
    while (l1 != NULL || l2 != NULL || carry != 0) {
        int sum = carry;
        if (l1 != NULL) {
            sum += l1->val;
            l1 = l1->next;
        }
        if (l2 != NULL) {
            sum += l2->val;
            l2 = l2->next;
        }
        carry = sum / 10;
        current->next = (struct ListNode*) malloc(sizeof(struct ListNode));
        current->next->val = sum % 10;
        current->next->next = NULL;
        current = current->next;
    }
    
    struct ListNode *result = dummy->next;
    free(dummy);
    return result;
}

                                            
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

                                            
class Solution {
    function addTwoNumbers($l1, $l2) {
        $dummyHead = new ListNode(0);
        $current = $dummyHead;
        $carry = 0;

        while ($l1 !== null || $l2 !== null || $carry !== 0) {
            $sum = $carry;
            if ($l1 !== null) {
                $sum += $l1->val;
                $l1 = $l1->next;
            }
            if ($l2 !== null) {
                $sum += $l2->val;
                $l2 = $l2->next;
            }
            
            $carry = intdiv($sum, 10);
            $current->next = new ListNode($sum % 10);
            $current = $current->next;
        }

        return $dummyHead->next;
    }
}

                                            
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let dummyHead = ListNode(0)
        var current = dummyHead
        var p = l1, q = l2
        var carry = 0
        
        while p != nil || q != nil {
            let x = p?.val ?? 0
            let y = q?.val ?? 0
            let sum = carry + x + y
            carry = sum / 10
            current.next = ListNode(sum % 10)
            current = current.next!
            if p != nil { p = p!.next }
            if q != nil { q = q!.next }
        }
        
        if carry > 0 {
            current.next = ListNode(carry)
        }
        
        return dummyHead.next
    }
}

                                            
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def add_two_numbers(l1, l2)
    dummy_head = ListNode.new(0)
    current = dummy_head
    carry = 0
    
    while l1 || l2 || carry > 0
        val1 = l1 ? l1.val : 0
        val2 = l2 ? l2.val : 0
        sum = val1 + val2 + carry
        carry = sum / 10
        current.next = ListNode.new(sum % 10)
        current = current.next
        
        l1 = l1.next if l1
        l2 = l2.next if l2
    end
    
    dummy_head.next
end

                                            
object Solution {
  def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
    var carry = 0
    val head = new ListNode(0)
    var current = head
    var p1 = l1
    var p2 = l2

    while (p1 != null || p2 != null || carry != 0) {
      val sum = (if (p1 != null) p1.x else 0) + (if (p2 != null) p2.x else 0) + carry
      carry = sum / 10
      current.next = new ListNode(sum % 10)
      current = current.next
      if (p1 != null) p1 = p1.next
      if (p2 != null) p2 = p2.next
    }

    head.next
  }
}

                                            
defmodule ListNode do
  @type t :: %__MODULE__{
          val: integer,
          next: t() | nil
        }
  defstruct val: 0, next: nil
end

defmodule Solution do
  def add_two_numbers(l1, l2) do
    add_lists(l1, l2, 0)
  end

  defp add_lists(%ListNode{val: v1, next: n1} = l1, %ListNode{val: v2, next: n2} = l2, carry) do
    sum = v1 + v2 + carry
    new_val = rem(sum, 10)
    carry = div(sum, 10)

    %ListNode{val: new_val, next: add_next(n1, n2, carry)}
  end

  defp add_lists(nil, nil, 0), do: nil
  defp add_lists(nil, nil, carry), do: %ListNode{val: carry}

  defp add_lists(nil, %ListNode{} = l2, carry), do: add_lists(%ListNode{val: 0}, l2, carry)
  defp add_lists(%ListNode{} = l1, nil, carry), do: add_lists(l1, %ListNode{val: 0}, carry)

  defp add_next(n1, n2, carry) do
    case {n1, n2, carry} do
      {nil, nil, 0} -> nil
      {_n1, _n2, _} -> add_lists(n1, n2, carry)
    end
  end
end

                                            
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    if (!l1 && !l2) return null;

    let dummy = new ListNode();
    let current = dummy;
    let carry = 0;

    while (l1 || l2 || carry > 0) {
        let sum = carry;
        if (l1) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2) {
            sum += l2.val;
            l2 = l2.next;
        }
        carry = Math.floor(sum / 10);
        sum = sum % 10;
        current.next = new ListNode(sum);
        current = current.next;
    }

    return dummy.next;
};

                                            
impl Solution {
    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode { val: 0, next: None }));
        let (mut p, mut q, mut current) = (l1, l2, dummy.as_mut());

        let mut carry = 0;

        while p.is_some() || q.is_some() {
            let sum = carry +
                p.as_ref().map_or(0, |node| node.val) +
                q.as_ref().map_or(0, |node| node.val);

            carry = sum / 10;

            current.as_mut().unwrap().next = Some(Box::new(ListNode { val: sum % 10, next: None }));
            current = current.and_then(|node| node.next.as_mut());

            if let Some(node) = p.as_mut() {
                p = node.next.take();
            }
            if let Some(node) = q.as_mut() {
                q = node.next.take();
            }
        }

        if carry > 0 {
            current.as_mut().unwrap().next = Some(Box::new(ListNode { val: carry, next: None }));
        }

        dummy.unwrap().next
    }
}

                                            
add_two_numbers(null, L2) -> L2;
add_two_numbers(L1, null) -> L1;
add_two_numbers(#list_node{val = V1, next = N1}, #list_node{val = V2, next = N2}) ->
    Sum = V1 + V2,
    {NewVal, Carry} = case Sum >= 10 of
        true -> {Sum rem 10, 1};
        false -> {Sum, 0}
    end,
    NewNode = #list_node{val = NewVal},
    NextL1 = if N1 =:= null -> null; true -> N1 end,
    NextL2 = if N2 =:= null -> null; true -> N2 end,
    NextNode = add_two_numbers(NextL1, NextL2),
    if
        Carry =:= 1 ->
            #list_node{val = NewVal, next = add_two_numbers(NextNode, #list_node{val = Carry, next = null})}
        ;
        true -> #list_node{val = NewVal, next = NextNode}
    end.

To solve this coding challenge, we need to create a function that will take two linked lists, each representing a non-negative integer (with digits stored in reverse order), and return a new linked list representing their sum.

Explanation

We'll implement the solution with the following approach:

Define the ListNode class : This class will represent each node in the linked list. Each node has a value (
val

) and a pointer (
next

) to the next node.
Initialize a dummy node : This dummy node will help us easily return the resulting linked list later. We will also have a current pointer (
curr

) initialized to this dummy node and a variable (
carry

) initialized to 0 to handle the carryover in the addition process.
Traverse both linked lists simultaneously : We'll use a while-loop to traverse both linked lists and continue until we've processed all nodes of both lists and handled any remaining carry.
Sum the corresponding nodes : For each node in both linked lists, add their values along with any carry from the previous addition. If any of the linked lists is shorter, treat the missing values as 0.
Calculate new digit and carry : Use the divmod function to get the new digit value (
val

) and the new carry. Append this digit to the resulting linked list.
Move to the next nodes : Move to the next nodes in both input linked lists (if available) and continue the process until all nodes are processed.
Return the result : Finally, return the linked list starting from the node next to the dummy node.

Here's an example in pseudocode that follows the detailed logic above: Detailed Steps in Pseudocode:

Define a class
ListNode

:

                                            
class ListNode:
# Constructor to initialize the node with a value and a next pointer
def __init__(self, val=0, next=None):
self.val = val  # Value of the node
self.next = next  # Pointer to the next node

Define the function
addTwoNumbers

which takes two linked lists
l1

and
l2

:

                                            
def addTwoNumbers(l1, l2):
# Initialize the dummy node and the current pointer
dummy = ListNode()
curr = dummy
carry = 0

# Loop until both linked lists are fully traversed and there is no carry left
while l1 is not null or l2 is not null or carry is not 0:
# Start with the carry value
total_sum = carry

# Add the values from the nodes of l1 and l2 if they exist
if l1 is not null:
total_sum = total_sum + l1.val
l1 = l1.next  # Move to the next node in l1

if l2 is not null:
total_sum = total_sum + l2.val
l2 = l2.next  # Move to the next node in l2

# Calculate the new digit and the new carry
carry, digit_value = divmod(total_sum, 10)

# Create a new node with the digit value and attach to the result linked list
curr.next = ListNode(val=digit_value)
curr = curr.next  # Move the current pointer to the new node

# Return the result linked list starting from the node after the dummy
return dummy.next

Explanation:

The
ListNode

class helps in building the nodes for the linked lists.
The
addTwoNumbers

function performs a parallel traversal of both input linked lists while managing the carry resulting from the addition. Each resulting digit is appended to a new linked list.
The use of a dummy node allows easy manipulation and return of the resulting linked list without special-case handling of the head node.

By following these steps, you can solve the challenge of adding two numbers represented by linked lists, ensuring both correctness and simplicity in managing the sum and carry of each digit.