Add Two Numbers Represented as Linked List in DSA Java - Build from Scratch

Add Two Numbers Represented as Linked List

📖 Scenario: You are working on a simple calculator app that adds two numbers. These numbers are stored in a special way: each digit is a node in a linked list, and the digits are stored in reverse order. For example, the number 342 is stored as 2 -> 4 -> 3 -> null.Your task is to add two such numbers and return the sum as a linked list in the same reversed format.

🎯 Goal: Build a Java program that creates two linked lists representing numbers, adds them digit by digit, and prints the resulting linked list showing the sum.

📋 What You'll Learn

Create two linked lists representing the numbers 342 and 465 respectively.

Create a variable to hold the carry during addition.

Write the logic to add the two linked lists digit by digit, handling carry.

Print the resulting linked list showing the sum in the format: digit -> digit -> ... -> null.

💡 Why This Matters

🌍 Real World

Adding large numbers digit by digit is useful in calculators, financial software, and systems where numbers exceed normal data type limits.

💼 Career

Understanding linked lists and how to manipulate them is important for software engineering roles, especially those involving data structures and algorithmic problem solving.

1

Create the first linked list representing the number 342

Create a linked list called l1 representing the number 342 in reverse order as 2 -> 4 -> 3 -> null. Use the provided ListNode class and create nodes with values 2, 4, and 3 linked accordingly.

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class AddTwoNumbers {
    public static void main(String[] args) {
        // Create linked list l1 representing 342
        // Your code here
    }
}

Hint

Remember to link the nodes so that l1 points to the first node with value 2, which points to 4, which points to 3.

2

Create the second linked list representing the number 465

Create a linked list called l2 representing the number 465 in reverse order as 5 -> 6 -> 4 -> null. Use the ListNode class and create nodes with values 5, 6, and 4 linked accordingly.

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class AddTwoNumbers {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);
        // Create linked list l2 representing 465
        // Your code here
    }
}

Hint

Link the nodes so that l2 points to 5, which points to 6, which points to 4.

3

Add the two linked lists digit by digit

Create a variable carry initialized to 0. Write a while loop that continues as long as l1, l2, or carry is not zero. Inside the loop, add the values of l1 and l2 nodes and the carry. Create new nodes for the result linked list with the digit value and update carry accordingly.

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class AddTwoNumbers {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        int carry = 0;
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        // Add digits from l1 and l2
        // Your code here
    }
}

Hint

Use a dummy head node to build the result list. Update carry after each addition. Move l1 and l2 forward if they are not null.

4

Print the resulting linked list showing the sum

Print the linked list starting from dummyHead.next in the format: digit -> digit -> ... -> null. Use a while loop to traverse the list and print each node's value followed by ->. End with null.

DSA Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class AddTwoNumbers {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        int carry = 0;
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;

        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        ListNode result = dummyHead.next;
        // Print the result linked list
        // Your code here
    }
}

Hint

Traverse the result linked list starting from dummyHead.next. Print each node's value followed by ->. After the last node, print null.

Practice

1. What does the problem "Add Two Numbers Represented as Linked List" mainly involve?

easy

A. Reversing a linked list

B. Sorting two linked lists in ascending order

C. Finding the middle node of a linked list

D. Adding digits node by node from two linked lists representing numbers

Solution

1. Step 1: Understand the problem context

   The problem involves two linked lists where each node contains a digit of a number, stored in reverse order.

2. Step 2: Identify the required operation

   We need to add these two numbers digit by digit, handling carry, and return the sum as a linked list.

3. Final Answer:

   Adding digits node by node from two linked lists representing numbers -> Option D

4. Quick Check:

   Adding digits node by node = D [OK]

Hint: Focus on digit-wise addition with carry [OK]

Common Mistakes:

• Confusing addition with sorting
• Ignoring carry during addition
• Assuming numbers are stored in forward order

2. Which of the following Java code snippets correctly initializes a new node for a singly linked list representing a digit?

easy

A. ListNode node = ListNode(5);

B. ListNode node = new ListNode(); node.next = 5;

C. ListNode node = new ListNode(5);

D. ListNode node = new ListNode.val(5);

Solution

1. Step 1: Recall Java object creation syntax

   In Java, to create a new object, use the 'new' keyword followed by the constructor call with parameters.

2. Step 2: Check each option for correct syntax

   ListNode node = new ListNode(5); uses 'new ListNode(5);' which is correct. ListNode node = ListNode(5); misses 'new'. ListNode node = new ListNode(); node.next = 5; incorrectly sets next instead of val. ListNode node = new ListNode.val(5); is invalid syntax.

3. Final Answer:

   ListNode node = new ListNode(5); -> Option C

4. Quick Check:

   Java new object syntax = B [OK]

Hint: Use 'new' keyword with constructor for object creation [OK]

Common Mistakes:

• Omitting 'new' keyword
• Incorrect constructor call syntax
• Trying to call constructor like a method without 'new'
• Confusing node.val and node.next

3. What is the output linked list after adding the two numbers represented by these linked lists? List 1: 2 -> 4 -> 3 -> null (represents 342) List 2: 5 -> 6 -> 4 -> null (represents 465)

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummy;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummy.next;
}

medium

A. 7 -> 0 -> 8 -> null

B. 8 -> 0 -> 7 -> null

C. 7 -> 10 -> 7 -> null

D. 2 -> 4 -> 3 -> 5 -> 6 -> 4 -> null

Solution

1. Step 1: Add digits node by node with carry

   Adding 2+5=7 (carry 0), 4+6=10 (carry 1), 3+4=7 plus carry 1 = 8.

2. Step 2: Construct the resulting linked list

   Digits are 7 (units), 0 (tens), 8 (hundreds), so linked list is 7 -> 0 -> 8 -> null.

3. Final Answer:

   7 -> 0 -> 8 -> null -> Option A

4. Quick Check:

   342 + 465 = 807 represented as 7->0->8 [OK]

Hint: Add digits with carry, build new nodes [OK]

Common Mistakes:

• Ignoring carry in addition
• Appending nodes incorrectly
• Mixing digit order in output

4. Identify the bug in this code snippet for adding two numbers represented as linked lists:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    int carry = 0;
    while (l1 != null && l2 != null) {
        int sum = carry + l1.val + l2.val;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        l1 = l1.next;
        l2 = l2.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummy.next;
}

medium

A. The carry is not calculated correctly

B. The while loop should use '||' instead of '&&' to handle different length lists

C. The dummy node is not initialized properly

D. The function does not return the correct node

Solution

1. Step 1: Analyze the loop condition

   The loop uses '&&' which stops when either list ends, missing remaining nodes of longer list.

2. Step 2: Correct loop condition to '||'

   Using '||' ensures the loop continues until both lists are fully processed, handling different lengths correctly.

3. Final Answer:

   The while loop should use '||' instead of '&&' to handle different length lists -> Option B

4. Quick Check:

   Loop condition must cover all nodes = A [OK]

Hint: Use '||' to process all nodes in both lists [OK]

Common Mistakes:

• Using '&&' causing early loop exit
• Not handling carry after loop
• Not advancing pointers correctly

5. Given two linked lists representing numbers in reverse order, how would you modify the addition algorithm to handle the case where the input lists are extremely long (millions of nodes) and memory is limited?

hard

A. Use iterative addition with constant extra space and process nodes one by one

B. Convert linked lists to integers, add, then convert back to linked list

C. Store all digits in arrays before adding to optimize speed

D. Reverse both lists first, add, then reverse the result

Solution

1. Step 1: Consider memory constraints with large inputs

   Converting to integers or arrays requires large memory, not feasible for millions of nodes.

2. Step 2: Use iterative addition with constant extra space

   Process nodes one by one, create result nodes on the fly, and avoid storing entire numbers in memory.

3. Final Answer:

   Use iterative addition with constant extra space and process nodes one by one -> Option A

4. Quick Check:

   Iterative node-wise addition saves memory = C [OK]

Hint: Add nodes one by one without full number conversion [OK]

Common Mistakes:

• Trying to convert entire list to integer causing overflow
• Using extra arrays increasing memory usage
• Reversing lists unnecessarily increasing complexity