Addition, But Make It Linked 🔗➕

Adding Two Numbers – One Node at a Time

We’ve all done basic addition, right? But what happens when each digit is stored in a linked list and… in reverse order? Welcome to a fan-favorite problem: Add Two Numbers (LeetCode #2).

Let’s dive into the different ways to tackle it in Java – from the tried-and-true iterative method to a cheeky BigInteger hack.

The best data structure for solving it (and why!)

The obvious MVP here? Singly Linked Lists. Since the digits are stored in reverse order (1’s place first), we can iterate from the head without reversing anything manually. We just need to simulate digit-by-digit addition — like we did in school, carry and all.

And for tracking the result? A dummy head node makes things a breeze. It helps keep the logic simple while chaining together the resulting nodes.

Different approaches – brute force to optimized solutions

1: Iterative (Most Common)

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;

            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
        }

        return dummy.next;
    }

2: Recursive

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return helper(l1, l2, 0);
    }

    private ListNode helper(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null && carry == 0) return null;

        int sum = carry;
        if (l1 != null) sum += l1.val;
        if (l2 != null) sum += l2.val;

        ListNode node = new ListNode(sum % 10);

        node.next = helper(
            l1 != null ? l1.next : null,
            l2 != null ? l2.next : null,
            sum / 10
        );

        return node;
    }
}

3: BigInteger (Cheeky but Fast for Quick Prototypes)

import java.math.BigInteger;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        BigInteger num1 = listToBigInteger(l1);
        BigInteger num2 = listToBigInteger(l2);
        BigInteger sum = num1.add(num2);
        return bigIntegerToList(sum);
    }

    private BigInteger listToBigInteger(ListNode node) {
        StringBuilder sb = new StringBuilder();
        while (node != null) {
            sb.insert(0, node.val);  // reverse order
            node = node.next;
        }
        return new BigInteger(sb.toString());
    }

    private ListNode bigIntegerToList(BigInteger num) {
        String str = new StringBuilder(num.toString()).reverse().toString();
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        for (char c : str.toCharArray()) {
            curr.next = new ListNode(c - '0');
            curr = curr.next;
        }
        return dummy.next;
    }
}

⚠️Common mistakes & pitfalls to avoid

  • Forgetting the final carry: After the loop ends, don’t forget to check if carry != 0. It needs to be added as a new node.

  • Mixing up digit order: The problem assumes the digits are in reverse order. Make sure not to reverse them unless specifically required.

  • Recursive stack overflow: For very long lists, recursion might blow the stack. The iterative version is safer for large inputs.

📊Time & Space complexity analysis

Iterative and Recursive Approaches:

  • Time: O(max(m, n))
    We go through each node once from both lists.

  • Space: O(max(m, n))
    One node per digit in the result, plus recursion stack (if recursive).

BigInteger Approach:

  • Time: O(n + m), but depends on internal BigInteger operations

  • Space: O(n + m) for string building and parsing

🌍Real-world applications

  • Embedded systems dealing with long numbers that can’t fit in standard data types.

  • Blockchain wallets where arithmetic on long digit sequences is common.

  • Custom calculators or compilers for user-defined numeric types.

  • And of course... your friendly neighborhood linked list interview questions


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Zero Array After Queries

Zero Array After Queries You are given an integer array nums and a list of queries, where each query is a pair [li, ri] representing a range. Each query allows you to decrement any subset of elements in the range [li, ri] by 1. Your task is to determine if it is possible to make every element in nums equal to zero after applying all queries in order . Example Input: nums = [ 1 , 0 , 1 ] queries = [[0, 2]] Output: true Explanation: We can select indices 0 and 2 and decrement both by 1 to obtain [0, 0, 0] . Best Data Structure for the Job We are working with multiple range updates and need to evaluate coverage over indices. The best choice here is the difference array combined with a prefix sum . It allows efficient range additions and helps track how many times each index is affected by the queries. Different Approaches Approach 1: Brute Force This naive method iterates over every index for every query and performs the decrement operations directly. class Solution {...
Read more