Add Two Numbers

This challenge involves implementing a function that adds two non-negative integers represented as linked lists. Each node in the linked list contains a single digit, and the digits are stored in reverse order (the most significant digit is at the head of the list). This problem is a common exercise for understanding linked list manipulation and handling potential carries in arithmetic.

Problem Description

You are given two non-empty linked lists, l1 and l2, representing two non-negative integers. The digits are stored in a way that the least significant digit is at the head of the list, and each node contains a single digit. Your task is to add the two numbers and return the sum as a linked list in the same format.

Key Requirements:

• The function should accept two linked lists, l1 and l2, as input.
• The function should return a new linked list representing the sum of the two input numbers.
• The digits in the returned linked list should also be stored in reverse order.
• The input numbers are non-negative.
• Assume the input numbers do not contain any leading zeros, except for the number 0 itself.

Expected Behavior:

The function should correctly simulate the manual process of adding two numbers column by column, including handling any carries to the next significant digit.

Edge Cases to Consider:

• One list might be significantly longer than the other.
• The sum might result in an extra digit at the most significant end (e.g., 5 + 5 = 10).
• Both input lists might represent the number 0.

Examples

Example 1:

Input: l1 = [2, 4, 3], l2 = [5, 6, 4]
Output: [7, 0, 8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]
Explanation: 0 + 0 = 0.

Example 3:

Input: l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]
Output: [8, 9, 9, 9, 0, 0, 0, 1]
Explanation: 9,999,999 + 9,999 = 10,009,998.

Constraints

• The number of nodes in each linked list is between 1 and 100.
• Each node's value is an integer between 0 and 9.
• The linked lists represent non-negative integers.
• The time complexity should ideally be O(max(N, M)), where N and M are the lengths of l1 and l2 respectively.
• The space complexity should ideally be O(max(N, M)) for the new linked list.

Notes

• You will need to define a ListNode structure or class to represent the nodes of the linked list. This structure typically contains a value (or data) field and a next pointer to the subsequent node.
• Consider how to handle the carry-over from one digit position to the next.
• Pay attention to what happens when one list runs out of nodes before the other.
• Think about how to construct the result linked list node by node.