#445

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Add Two Numbers II

Add Two Numbers II involves summing two numbers represented as linked lists and returning the result as a new linked list.

linked list math stack

Problem Statement

Given two non-empty linked lists representing two non-negative integers, where each node contains a single digit, the digits are stored in reverse order, and the most significant digit comes first. Add the two numbers and return the result as a linked list in the same format.

You may assume the two numbers do not contain any leading zero, except the number 0 itself. The linked lists' lengths range from 1 to 100, and each digit is between 0 and 9. Ensure to handle carry during the addition process and return the final sum as a linked list.

Examples

Example 1

Input: l1 = [7,2,4,3], l2 = [5,6,4]

Output: [7,8,0,7]

Example details omitted.

Example 2

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [8,0,7]

Example details omitted.

Example 3

Input: l1 = [0], l2 = [0]

Output: [0]

Example details omitted.

Constraints

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Solution Approach

Reverse Both Lists

Reverse both input linked lists to simplify addition, making it similar to adding numbers from right to left, as with typical addition from least significant to most significant digit.

Use a Stack for Carry

Use a stack to track the carry and facilitate the addition of corresponding digits from both lists. This helps to manage the addition without needing to reverse the lists again.

Rebuild the Result List

Once the addition is complete, rebuild the result linked list in the correct order by reversing the resulting digits, and ensure proper carry handling.

Complexity Analysis

Metric	Value
Time	O(m + n)
Space	O(m + n)

The time complexity of O(m + n) arises from traversing both linked lists, where m and n are the lengths of the two lists. The space complexity is also O(m + n) due to storing the result list and the carry stack.

What Interviewers Usually Probe

The candidate demonstrates a clear understanding of linked-list manipulation and pointer handling.
The candidate effectively handles edge cases such as carry and varying list lengths.
The candidate optimizes the solution to avoid unnecessary reversals of the lists.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the carry between nodes during the addition.
Not managing the stack correctly, leading to incorrect carry calculations.
Reversing the result list unnecessarily or missing the final carry node.

Follow-up variants

Add numbers represented in reverse order (least significant digit first).
Add numbers where digits are stored in a different order, requiring a different traversal strategy.
Handle larger numbers, requiring efficient use of memory and stack operations.

FAQ

What is the time complexity of the Add Two Numbers II problem?

The time complexity is O(m + n), where m and n are the lengths of the two linked lists.

How do we handle carry in the Add Two Numbers II problem?

We use a stack to manage carry while adding corresponding digits of the two lists, ensuring the correct result is obtained.

Can this problem be solved without reversing the linked lists?

Yes, but reversing the lists simplifies the solution and eliminates the need for extra complexity in handling digits from most significant to least significant.

What should we do if the linked lists have different lengths?

If the linked lists have different lengths, we pad the shorter list with zeros at the front before proceeding with the addition.

What is the primary pattern in the Add Two Numbers II problem?

The primary pattern involves linked-list pointer manipulation, where we traverse the lists and handle carry effectively during the addition.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# 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]:
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next
        dummy = ListNode()
        carry = 0
        while s1 or s2 or carry:
            s = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry
            carry, val = divmod(s, 10)
            # node = ListNode(val, dummy.next)
            # dummy.next = node
            dummy.next = ListNode(val, dummy.next)
        return dummy.next

Solution 2

#### Rust

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# 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]:
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next
        dummy = ListNode()
        carry = 0
        while s1 or s2 or carry:
            s = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry
            carry, val = divmod(s, 10)
            # node = ListNode(val, dummy.next)
            # dummy.next = node
            dummy.next = ListNode(val, dummy.next)
        return dummy.next

Continue Practicing

#382 linked list random node #234 palindrome linked list #227 basic calculator ii