Leetcode 2: Add Two numbers

Introduction

LeetCode Problem 2, “Add Two Numbers,” is a popular problem that involves linked lists. The problem can be summarized as follows:

Problem Statement:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

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]

Possible Solutions

Approach 1: Iterative Method

Algorithm:

Initialize a dummy head to help with the resulting linked list.
Initialize a current pointer to the dummy head and a carry variable to 0.
Iterate through both linked lists until both are exhausted and there is no carry left:
- Sum the current digits of both lists along with the carry.
- Update the carry.
- Create a new node with the sum modulo 10.
- Move the current pointer and the pointers of the input lists to their next nodes.
Return the linked list starting from the node next to the dummy head.

Time and Space Complexity:

Time Complexity: O(max(m, n)), where m and n are the lengths of the two linked lists. We traverse both lists at most once.
Space Complexity: O(max(m, n)), which is the space for the resulting linked list.

Python Code:

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

def addTwoNumbers(l1, l2):
    dummy_head = ListNode()
    current = dummy_head
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        total = val1 + val2 + carry
        carry = total // 10
        current.next = ListNode(total % 10)

        current = current.next
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy_head.next


One of the fastest solution in terms of run time is below:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        op = opHead = ListNode()
        s = 0

        while l1 or l2 or s:
            op.next = ListNode()
            op = op.next

            s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
            s, op.val = divmod(s, 10)

            l1 = l1.next if l1 else False
            l2 = l2.next if l2 else False

        return opHead.next

Edge Cases

Edge Case 1: Different Lengths of Lists

Example: l1 = [2, 4], l2 = [5, 6, 4]
Explanation: The algorithm will handle lists of different lengths by treating the missing nodes as zero.

Edge Case 2: Carry at the End

Example: l1 = [9, 9], l2 = [1]
Explanation: The sum is 100, so the output should be [0, 0, 1]. The algorithm adds an additional node if there is a carry left after processing both lists.

Edge Case 3: One List is Empty

Example: l1 = [], l2 = [0, 1]
Explanation: The algorithm treats the empty list as zero and returns the non-empty list.

Edge Case 4: Both Lists are Empty

Example: l1 = [], l2 = []
Explanation: The algorithm should handle this by returning a single node with value 0.

Handling Edge Cases in Code

def addTwoNumbers(l1, l2):
    dummy_head = ListNode()
    current = dummy_head
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        total = val1 + val2 + carry
        carry = total // 10
        current.next = ListNode(total % 10)

        current = current.next
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy_head.next

# Test cases for edge cases
# Case 1: Different lengths
l1 = ListNode(2, ListNode(4))
l2 = ListNode(5, ListNode(6, ListNode(4)))
print_linked_list(addTwoNumbers(l1, l2)) # Expected: [7, 0, 5]

# Case 2: Carry at the end
l1 = ListNode(9, ListNode(9))
l2 = ListNode(1)
print_linked_list(addTwoNumbers(l1, l2)) # Expected: [0, 0, 1]

# Case 3: One list empty
l1 = None
l2 = ListNode(0, ListNode(1))
print_linked_list(addTwoNumbers(l1, l2)) # Expected: [0, 1]

# Case 4: Both lists empty
l1 = None
l2 = None
print_linked_list(addTwoNumbers(l1, l2)) # Expected: [0]

To print the linked list in the test cases, you would need a helper function:

def print_linked_list(node):
    while node:
        print(node.val, end=" -> " if node.next else "\n")
        node = node.next

In conclusion, the iterative method provides an efficient and straightforward way to solve the “Add Two Numbers” problem on LeetCode. By carefully handling edge cases, we ensure the robustness and correctness of our solution.

Menu