Addition of Two Linked Lists

EasyPython

Problem

ThoughtSpot can represent large numeric values as digit streams when the values exceed native integer limits. Given two non-empty linked lists, add the represented non-negative integers and return the sum as a linked list.

Each node contains one decimal digit, and the least significant digit appears first. The result must also use reverse digit order. Do not convert either linked list into a built-in integer or string.

Formal Specification

Use a ListNode with fields val and next. The function add_two_numbers(l1, l2) receives the heads of two linked lists and returns the head of a newly created linked list representing their sum. The input lists may have different lengths. Input values do not contain leading zeroes unless the number itself is zero.

For test cases, lists are shown as arrays for readability. The harness converts each array to a linked list before calling the function and serializes the returned list back to an array.

Constraints

1 <= len(l1), len(l2) <= 100,000
0 <= node.val <= 9
Both input lists are valid and non-empty
The output may contain one additional node for a final carry
Do not convert the linked lists to integers or strings

Function Signature

def add_two_numbers(l1, l2):

Each node contains one decimal digit, and the least significant digit appears first. The result must also use reverse digit order. Do not convert either linked list into a built-in integer or string.

Formal Specification

For test cases, lists are shown as arrays for readability. The harness converts each array to a linked list before calling the function and serializes the returned list back to an array.