You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:
A large-scale financial or transaction-processing system stores very large numbers in a distributed format. To avoid integer overflow and to support arbitrary precision, numbers are represented as linked lists, where each node stores a single digit.
The digits are stored in reverse order, meaning the least significant digit comes first.
Each linked list represents a non-negative integer.
The system needs to add two such numbers and return the result in the same linked-list format, handling digit-wise addition and carry propagation correctly.
This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
You are given two non-empty linked lists l1 and l2 representing two non-negative integers.
- The digits are stored in reverse order
- Each node contains a single digit
Add the two numbers and return the sum as a linked list, also in reverse order.
Input Format
l1: head of the first linked listl2: head of the second linked list
Each node is defined as:
ListNode { int val; ListNode next; }
Output Format
- Return the head of a linked list representing the sum
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]
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]