Add Two Numbers Represented as Linked List in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Adding Two Linked Lists Representing Numbers

What is the output linked list after adding the two numbers represented by these linked lists?

List 1: 2 -> 4 -> 3 -> null
List 2: 5 -> 6 -> 4 -> null

Note: Each node contains a single digit and digits are stored in reverse order.

DSA Python

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

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    current = dummy
    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.next

# Construct lists
l1 = ListNode(2, ListNode(4, ListNode(3)))
l2 = ListNode(5, ListNode(6, ListNode(4)))

result = addTwoNumbers(l1, l2)
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)

A [7, 10, 7]

B [8, 0, 7]

C [7, 0, 8]

D [5, 10, 7]

💡 Hint

Add digits node by node, remember to carry over if sum >= 10.

Adding 342 + 465 gives 807. Since digits are reversed, output list is 7 -> 0 -> 8 -> null.

❓ Predict Output

intermediate

Result of Adding Unequal Length Linked Lists

What is the output linked list after adding these two numbers?

List 1: 9 -> 9 -> 9 -> 9 -> null
List 2: 1 -> null

Digits are stored in reverse order.

DSA Python

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

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    current = dummy
    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.next

l1 = ListNode(9, ListNode(9, ListNode(9, ListNode(9))))
l2 = ListNode(1)

result = addTwoNumbers(l1, l2)
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)

A [0, 0, 0, 0, 1]

B [0, 0, 0, 1]

C [1, 0, 0, 0, 0]

D [9, 9, 9, 10]

💡 Hint

Remember to carry over after the last node if needed.

9999 + 1 = 10000, so the linked list is 0 -> 0 -> 0 -> 0 -> 1 -> null.

🔧 Debug

advanced

Identify the Error in Linked List Addition Code

What error will this code raise when adding two linked lists?

Code snippet:

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    current = dummy
    carry = 0
    while l1 or l2:
        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
    if carry:
        current.next = ListNode(carry)
    return dummy.next

A SyntaxError: invalid syntax

B AttributeError: 'NoneType' object has no attribute 'val'

C No error, code runs correctly

D TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

💡 Hint

Check the while loop condition and what happens when l1 or l2 is None.

The loop condition misses the carry check, so when l1 and l2 become None but carry is non-zero, accessing l1.val or l2.val causes AttributeError.

❓ Predict Output

advanced

Output When Adding Lists with Zero Nodes

What is the output linked list after adding these two numbers?

List 1: 0 -> null
List 2: 0 -> null

Digits are stored in reverse order.

DSA Python

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

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    current = dummy
    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.next

l1 = ListNode(0)
l2 = ListNode(0)

result = addTwoNumbers(l1, l2)
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)

A [0]

B []

C [1]

D [0, 0]

💡 Hint

Adding zero plus zero should give zero.

0 + 0 = 0, so the output list is a single node with 0.

❓ Predict Output

expert

Output of Adding Large Numbers with Multiple Carries

What is the output linked list after adding these two numbers?

List 1: 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> null
List 2: 9 -> 9 -> 9 -> 9 -> null

Digits are stored in reverse order.

DSA Python

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

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    current = dummy
    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.next

l1 = ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))))
l2 = ListNode(9, ListNode(9, ListNode(9, ListNode(9))))

result = addTwoNumbers(l1, l2)
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)

A [8, 9, 9, 9, 9, 9, 9, 1]

B [8, 9, 9, 9, 0, 0, 1]

C [0, 9, 9, 9, 0, 0, 0, 1]

D [8, 9, 9, 9, 0, 0, 0, 1]

💡 Hint

Add digit by digit with carry, carefully track carries beyond the shorter list.

9999999 + 9999 = 10009998, reversed digits are 8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1 -> null.

Practice

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

easy

A. Adding two numbers where each digit is stored in a node of a linked list

B. Sorting two linked lists in ascending order

C. Finding the middle node of a linked list

D. Reversing a linked list

Solution

1. Step 1: Understand the problem context

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

2. Step 2: Identify the main 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 two numbers where each digit is stored in a node of a linked list -> Option A

4. Quick Check:

   Adding digits node-wise = Adding numbers represented as linked lists [OK]

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

Common Mistakes:

• Confusing addition with sorting
• Thinking the digits are stored in normal order
• Ignoring carry during addition

2. Which of the following is the correct way to create a node class for a singly linked list in Python for this problem?

easy

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

B. class Node:
def __init__(self, val, next):
val = self.val
next = self.next

C. class Node:
def __init__(self):
self.value = 0
self.next = None

D. class Node:
def __init__(self, val):
self.val = val
self.next = val

Solution

1. Step 1: Check correct attribute assignment

   class Node: def __init__(self, val=0, next=None): self.val = val self.next = next correctly assigns the value and next pointer using self.val and self.next.

2. Step 2: Verify default parameters and syntax

   class Node: def __init__(self, val=0, next=None): self.val = val self.next = next uses default values and proper syntax for linked list node creation.

3. Final Answer:

   class Node: def __init__(self, val=0, next=None): self.val = val self.next = next -> Option A

4. Quick Check:

   Correct node class syntax = class Node: def __init__(self, val=0, next=None): self.val = val self.next = next [OK]

Hint: Use self to assign attributes inside __init__ [OK]

Common Mistakes:

• Reversing assignment order (val = self.val)
• Forgetting to use self for attributes
• Incorrect default parameters

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

def addTwoNumbers(l1, l2):
    carry = 0
    dummy = Node(0)
    current = dummy
    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 = Node(total % 10)
        current = current.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    return dummy.next

medium

A. 7 -> 10 -> 7 -> null

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

C. 2 -> 0 -> 8 -> null

D. 7 -> 0 -> 8 -> null

Solution

1. Step 1: Add digits with carry

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

2. Step 2: Form the resulting linked list

   Digits are 7 -> 0 -> 8 representing 807, which is 342+465.

3. Final Answer:

   7 -> 0 -> 8 -> null -> Option D

4. Quick Check:

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

Hint: Add digits and carry, build new nodes for sum digits [OK]

Common Mistakes:

• Not handling carry correctly
• Mixing digit order in output
• Adding digits without carry

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

def addTwoNumbers(l1, l2):
    carry = 0
    dummy = Node(0)
    current = dummy
    while l1 or l2:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        current.next = Node(total % 10)
        current = current.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    return dummy.next

medium

A. The initial dummy node is not created

B. The loop misses processing carry after both lists end

C. The nodes are not linked properly

D. The carry is not calculated correctly

Solution

1. Step 1: Analyze loop condition

   The loop runs only while l1 or l2 exist, but if carry remains after both end, it is ignored.

2. Step 2: Identify missing carry handling

   Carry should be checked in loop condition to add an extra node if needed.

3. Final Answer:

   The loop misses processing carry after both lists end -> Option B

4. Quick Check:

   Loop must include carry to avoid missing last digit [OK]

Hint: Include carry in loop condition to handle last digit [OK]

Common Mistakes:

• Ignoring carry after lists end
• Wrong loop condition
• Not updating current pointer

5. Given two linked lists representing numbers in reverse order, how would you modify the addition function to handle numbers stored in forward order (most significant digit first)?

hard

A. Use recursion to add digits from head to tail without reversing

B. Add digits directly without reversing, starting from head

C. Reverse both lists, add as usual, then reverse the result

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

Solution

1. Step 1: Understand digit order difference

   Forward order means most significant digit is at head, so addition must start from tail.

2. Step 2: Reverse lists to reuse existing logic

   Reversing lists makes digits least significant first, allowing normal addition and then reversing result restores order.

3. Final Answer:

   Reverse both lists, add as usual, then reverse the result -> Option C

4. Quick Check:

   Reverse to handle forward order addition [OK]

Hint: Reverse lists to reuse reverse-order addition logic [OK]

Common Mistakes:

• Adding digits from head without reversing
• Ignoring digit order difference
• Converting to int may cause overflow