LeetCode 2, Add Two Numbers, asks you to add two non-negative integers stored as linked lists. The four Kotlin versions below are iterative, recursive, functional, and tail-recursive.
What Is the Add Two Numbers Problem?
You have two non-empty linked lists. Each represents a non-negative integer, stored in reverse order, and each node holds one digit. Add the two numbers and return the sum as a linked list. Reverse order means you start at the least significant digit and carry forward, without reversing either list first.
You can assume that the two numbers don’t have any leading zeros, except for the number 0 itself.
ListNode representation
class ListNode(var `val`: Int) {
var next: ListNode? = null
}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]
Constraints
- The number of nodes in each linked list is in the range [1, 100]
- 0 ≤ Node.val ≤ 9
- It is guaranteed that the list represents a number that does not have leading zeros
What the problem tests
LeetCode 2 tests linked-list updates, carry, and the choice between an iterative and a recursive walk.
Unlike an array problem, you move through nodes. The awkward cases are unequal lengths and a final carry, such as 9999 + 1. The iterative and recursive versions make that trade-off differently.
Solution 1: Iterative Approach with Carry Handling
The iterative version walks both lists, adds the digits, and carries the overflow.
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
val dummy = ListNode(0)
var current = dummy
var carry = 0
var p1 = l1
var p2 = l2
while (p1 != null || p2 != null || carry != 0) {
val x = p1?.`val` ?: 0
val y = p2?.`val` ?: 0
val sum = carry + x + y
carry = sum / 10
current.next = ListNode(sum % 10)
current = current.next!!
p1 = p1?.next
p2 = p2?.next
}
return dummy.next
}
}How It Works
- Initialize: Create a dummy node to simplify list construction and track carry
- Iterate: Process both lists simultaneously until both are exhausted and no carry remains
- Calculate: For each position, add the digits from both lists plus any carry
- Update: Set the new carry and create a node with the digit (sum % 10)
- Advance: Move to the next nodes in both lists
Time and Space Complexity
- Time Complexity: O(max(m, n)) where m and n are the lengths of the input lists
- Space Complexity: O(max(m, n)) for the result list
Solution 2: Recursive Approach
The recursive version does the addition on the call stack. It is shorter if you already think in recursive calls.
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?, carry: Int = 0): ListNode? {
// Base case: both lists are null and no carry
if (l1 == null && l2 == null && carry == 0) {
return null
}
val sum = carry + (l1?.`val` ?: 0) + (l2?.`val` ?: 0)
val result = ListNode(sum % 10)
result.next = addTwoNumbers(l1?.next, l2?.next, sum / 10)
return result
}
}How It Works
- Base Case: Return null when both lists are exhausted and no carry remains
- Calculate: Add current digits and carry
- Create Node: Make a new node with the digit value
- Recurse: Call the function recursively for the next nodes with the new carry
Time and Space Complexity
- Time Complexity: O(max(m, n))
- Space Complexity: O(max(m, n)) due to recursion stack and result list
Solution 3: Functional Kotlin Approach
The functional version uses a Kotlin scope function:
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
fun addWithCarry(node1: ListNode?, node2: ListNode?, carry: Int): ListNode? {
if (node1 == null && node2 == null && carry == 0) return null
val sum = (node1?.`val` ?: 0) + (node2?.`val` ?: 0) + carry
return ListNode(sum % 10).apply {
next = addWithCarry(node1?.next, node2?.next, sum / 10)
}
}
return addWithCarry(l1, l2, 0)
}
}.apply sets next on the new node.
Solution 4: Tail-Recursive Optimization
The tail-recursive version is for large inputs, where a normal recursive call would grow the stack:
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
val dummy = ListNode(0)
tailrec fun addNodes(
node1: ListNode?,
node2: ListNode?,
carry: Int,
current: ListNode
) {
if (node1 == null && node2 == null && carry == 0) return
val sum = (node1?.`val` ?: 0) + (node2?.`val` ?: 0) + carry
current.next = ListNode(sum % 10)
addNodes(node1?.next, node2?.next, sum / 10, current.next!!)
}
addNodes(l1, l2, 0, dummy)
return dummy.next
}
}Which Edge Cases Should You Handle?
When implementing this solution, ensure that it handles these edge cases:
- Different length lists: [99] + [9] = [8, 0, 1]
- Carry at the end: [5] + [5] = [0,1]
- Single digit: [0] + [0] = [0]
- Multiple carries: [9,9,9] + [9,9,9] = [8,9,9,1]
How Do You Test Your Solution?
A Kotlin test suite:
fun main() {
val solution = Solution()
// Test case 1: [2,4,3] + [5,6,4] = [7,0,8]
val l1 = ListNode(2).apply {
next = ListNode(4).apply {
next = ListNode(3)
}
}
val l2 = ListNode(5).apply {
next = ListNode(6).apply {
next = ListNode(4)
}
}
val result = solution.addTwoNumbers(l1, l2)
printList(result) // Should print: 7 -> 0 -> 8
// Add more test cases...
}
fun printList(head: ListNode?) {
var current = head
val values = mutableListOf<Int>()
while (current != null) {
values.add(current.`val`)
current = current.next
}
println(values.joinToString(" -> "))
}Table comparison of solutions
| Approach | Time Complexity | Space Complexity | Pros | Cons |
|-----------------|----------------|------------------|--------------------|---------------------|
| Iterative | O(max(m,n)) | O(max(m,n)) | Simple, efficient | More verbose |
| Recursive | O(max(m,n)) | O(max(m,n)) | Elegant, concise | Stack overflow risk |
| Functional | O(max(m,n)) | O(max(m,n)) | Idiomatic Kotlin | May be less familiar|
| Tail-Recursive | O(max(m,n)) | O(max(m,n)) | Stack-safe | More complex |Happy coding!
David Cruz
davthecoder.com paglipat.com
LeetCode 2, Add Two Numbers, pide sumar dos enteros no negativos guardados como listas enlazadas. Las cuatro versiones en Kotlin de abajo son la iterativa, la recursiva, la funcional y la de recursión de cola.
¿Qué es el problema Add Two Numbers?
Tienes dos listas enlazadas que no están vacías. Cada una representa un entero no negativo, guardado en orden inverso, y cada nodo tiene un solo dígito. Suma los dos números y devuelve la suma como una lista enlazada. El orden inverso significa que empiezas por el dígito menos significativo y arrastras el acarreo, sin invertir ninguna de las dos listas antes.
Puedes dar por hecho que los dos números no llevan ceros a la izquierda, salvo el propio número 0.
Representación de ListNode
class ListNode(var `val`: Int) {
var next: ListNode? = null
}Ejemplos
Ejemplo 1:
- Entrada: l1 = [2,4,3], l2 = [5,6,4]
- Salida: [7, 0, 8]
- Explicación: 342 + 465 = 807
Ejemplo 2:
- Entrada: l1 = [0], l2 = [0]
- Salida: [0]
Ejemplo 3:
- Entrada: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
- Salida: [8,9,9,9,0,0,0,1]
Restricciones
- El número de nodos de cada lista enlazada está en el rango [1, 100]
- 0 ≤ Node.val ≤ 9
- Se garantiza que la lista representa un número que no tiene ceros a la izquierda
Qué pone a prueba el problema
LeetCode 2 pone a prueba las actualizaciones de una lista enlazada, el acarreo y la elección entre un recorrido iterativo y uno recursivo.
A diferencia de un problema de arrays, aquí avanzas por nodos. Los casos incómodos son las longitudes distintas y un acarreo final, como 9999 + 1. Las versiones iterativa y recursiva resuelven ese compromiso de forma distinta.
Solución 1: enfoque iterativo con gestión del acarreo
La versión iterativa recorre las dos listas, suma los dígitos y arrastra el acarreo.
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
val dummy = ListNode(0)
var current = dummy
var carry = 0
var p1 = l1
var p2 = l2
while (p1 != null || p2 != null || carry != 0) {
val x = p1?.`val` ?: 0
val y = p2?.`val` ?: 0
val sum = carry + x + y
carry = sum / 10
current.next = ListNode(sum % 10)
current = current.next!!
p1 = p1?.next
p2 = p2?.next
}
return dummy.next
}
}Cómo funciona
- Inicializa: crea un nodo ficticio para simplificar la construcción de la lista y lleva la cuenta del acarreo
- Itera: procesa las dos listas a la vez hasta que ambas se agoten y no quede acarreo
- Calcula: en cada posición, suma los dígitos de las dos listas más el acarreo que haya
- Actualiza: fija el acarreo nuevo y crea un nodo con el dígito (sum % 10)
- Avanza: pasa a los nodos siguientes de las dos listas
Complejidad temporal y espacial
- Complejidad temporal: O(max(m, n)), donde m y n son las longitudes de las listas de entrada
- Complejidad espacial: O(max(m, n)), por la lista resultado
Solución 2: enfoque recursivo
La versión recursiva hace la suma en la pila de llamadas. Queda más corta si ya piensas en llamadas recursivas.
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?, carry: Int = 0): ListNode? {
// Base case: both lists are null and no carry
if (l1 == null && l2 == null && carry == 0) {
return null
}
val sum = carry + (l1?.`val` ?: 0) + (l2?.`val` ?: 0)
val result = ListNode(sum % 10)
result.next = addTwoNumbers(l1?.next, l2?.next, sum / 10)
return result
}
}Cómo funciona
- Caso base: devuelve null cuando las dos listas se han agotado y no queda acarreo
- Calcula: suma los dígitos actuales y el acarreo
- Crea el nodo: construye un nodo nuevo con el valor del dígito
- Recurre: llama a la función de forma recursiva para los nodos siguientes, con el acarreo nuevo
Complejidad temporal y espacial
- Complejidad temporal: O(max(m, n))
- Complejidad espacial: O(max(m, n)), por la pila de recursión y la lista resultado
Solución 3: enfoque funcional en Kotlin
La versión funcional usa una función de ámbito de Kotlin:
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
fun addWithCarry(node1: ListNode?, node2: ListNode?, carry: Int): ListNode? {
if (node1 == null && node2 == null && carry == 0) return null
val sum = (node1?.`val` ?: 0) + (node2?.`val` ?: 0) + carry
return ListNode(sum % 10).apply {
next = addWithCarry(node1?.next, node2?.next, sum / 10)
}
}
return addWithCarry(l1, l2, 0)
}
}.apply asigna next en el nodo nuevo.
Solución 4: optimización con recursión de cola
La versión con recursión de cola es para entradas grandes, donde una llamada recursiva normal haría crecer la pila:
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
val dummy = ListNode(0)
tailrec fun addNodes(
node1: ListNode?,
node2: ListNode?,
carry: Int,
current: ListNode
) {
if (node1 == null && node2 == null && carry == 0) return
val sum = (node1?.`val` ?: 0) + (node2?.`val` ?: 0) + carry
current.next = ListNode(sum % 10)
addNodes(node1?.next, node2?.next, sum / 10, current.next!!)
}
addNodes(l1, l2, 0, dummy)
return dummy.next
}
}¿Qué casos límite debes cubrir?
Cuando implementes esta solución, asegúrate de que aguanta estos casos límite:
- Listas de distinta longitud: [99] + [9] = [8, 0, 1]
- Acarreo al final: [5] + [5] = [0,1]
- Un solo dígito: [0] + [0] = [0]
- Varios acarreos: [9,9,9] + [9,9,9] = [8,9,9,1]
¿Cómo pruebas tu solución?
Una batería de pruebas en Kotlin:
fun main() {
val solution = Solution()
// Test case 1: [2,4,3] + [5,6,4] = [7,0,8]
val l1 = ListNode(2).apply {
next = ListNode(4).apply {
next = ListNode(3)
}
}
val l2 = ListNode(5).apply {
next = ListNode(6).apply {
next = ListNode(4)
}
}
val result = solution.addTwoNumbers(l1, l2)
printList(result) // Should print: 7 -> 0 -> 8
// Add more test cases...
}
fun printList(head: ListNode?) {
var current = head
val values = mutableListOf<Int>()
while (current != null) {
values.add(current.`val`)
current = current.next
}
println(values.joinToString(" -> "))
}Tabla comparativa de las soluciones
| Approach | Time Complexity | Space Complexity | Pros | Cons |
|-----------------|----------------|------------------|--------------------|---------------------|
| Iterative | O(max(m,n)) | O(max(m,n)) | Simple, efficient | More verbose |
| Recursive | O(max(m,n)) | O(max(m,n)) | Elegant, concise | Stack overflow risk |
| Functional | O(max(m,n)) | O(max(m,n)) | Idiomatic Kotlin | May be less familiar|
| Tail-Recursive | O(max(m,n)) | O(max(m,n)) | Stack-safe | More complex |¡Feliz programación!
David Cruz
davthecoder.com paglipat.com
Loading comments…Cargando comentarios…