Katkat
Back

Add Two Forward-Order Lists

BloombergSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to perform manual addition on numbers represented by linked lists where the most significant digit comes first, requiring either stack-based reversal or recursive backtracking.

Add Two Forward-Order Lists

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in forward order, meaning the most significant digit is at the head of the list. Your task is to add the two numbers and return the sum as a linked list in the same forward-order format.

Constraints

  • The number of nodes in each list is in the range [1, 100].
  • Each node value is an integer between 0 and 9.
  • It is guaranteed that the lists do not contain leading zeros unless the number itself is 0.

Function Signature

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

def add_two_numbers(l1: ListNode, l2: ListNode) -> ListNode:

Examples

Example 1: Input: l1 = [7, 2, 4, 3], l2 = [5, 6, 4] Output: [7, 8, 0, 7] Explanation: 7243 + 564 = 7807

Example 2: Input: l1 = [2, 4, 3], l2 = [5, 6, 4] Output: [8, 0, 7] Explanation: 243 + 564 = 807

Edge Cases

  • Lists of different lengths.
  • A final carry that requires creating a new head node (e.g., 99 + 1 = 100).
  • Lists with single nodes.

Hints

Hint 1

Since the lists are in forward order, the last digits must be added first, which suggests using a stack or recursion to process nodes from end to beginning.

Hint 2

If you use two stacks to store the digits of each list, you can pop them one by one to simulate addition from right to left while keeping track of the carry.

Hint 3

Alternatively, you can pad the shorter list with leading zeros to make both lists equal in length before processing them recursively.

Follow-up questions

  • Can you solve this problem in O(n) time complexity using only O(1) extra space (excluding the output list)?
  • What if the input lists are very large and cannot fit into memory? How would you handle this if they are stored in files?
  • How would your approach change if the linked lists were allowed to contain negative integers?