### View *Add Two Numbers* on LeetCode

## Statistics

**Time Spent Coding**

5 minutes

**Time Complexity**

O(n+m+k) - We must iterate through each digit of the number in `l1`

(n) the number in `l2`

(m) and the sum of those numbers (k), resulting in the O(n+m+k) time complexity.

**Space Complexity**

O(k) - The length of the sum of the numbers stored in l1 and l2 is the number of `ListNode`

’s needed, resulting in the O(k) space complexity.

**Runtime Beats**

56.69% of other submissions

**Memory Beats**

69.95% of other sumbissions

## Explanation

Since each input is a linked list and not a number, the function `buildNum`

is created to convert the input linked list to a number.

The function `buildNum`

takes in a linked list and builds the entire number it contains. It does this by converting each digit from the linked list into a string and adding it to the front of the `res`

string since the number is represented backward in the linked lists (e.g. 1 -> 2 = 21). Once the number is built, it is converted into an integer and returned.

Run this function for `l1`

and `l2`

and store their results in `n1`

and `n2`

. Add them, store the result in `tot`

, and convert it into a string.

Initialize `head`

as a `ListNode`

and create a pointer to help incrementally add to the linked list.

Begin iterating backward (`[::-1]`

) through each digit in the `tot`

string and place its integer representation into a new `ListNode.`

Then make the node at the pointer point to the new node, and move the pointer to this new node.

Once the `tot`

string has been fully iterated, `return head.next`

this is because the head node contains an empty ListNode, which would add a `0`

to the front of the linked list.

## Data Structure Used

**Linked List -** Similar to a list or an array, except the data allocated for the list is generated as each new node is added, meaning the memory for the entire list may not be in consecutive memory. A linked list can not be indexed and must be traversed using a pointer.

## Solution

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
26
27
28
29
30

# 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]:
def buildNum(linked_list):
res = ''
while linked_list != None:
res = str(linked_list.val) + res
linked_list = linked_list.next
return int(res)
n1 = buildNum(l1)
n2 = buildNum(l2)
tot = str(n1 + n2)
head = ListNode()
pointer = head
for n in tot[::-1]:
new = ListNode()
new.val = int(n)
pointer.next = new
pointer = pointer.next
return head.next