LeetCode's challenge #2 asks us to sum up two Linked Lists and return one singly Linked List. The given lists are `(2 -> 4 -> 3)`

and `(5 -> 6 -> 4)`

, and the expected return list is `(7 -> 0 -> 8)`

.

### The Brute Force Solution

The brute force solution for this problem is not really worse than the optimized solution. Both have a space and time complexity of O(n) where n is the combined nodes in both lists.

The difference between the approaches is the unnecessary overhead of the first one. Swift does not come with a native **LinkedList**, therefore one would have to **implement the traversal**, then **traverse both lists** to get two integer arrays and **then sum up the elements**. Lastly, we have to **create and return the final list**.

Traversing each list means there are two linear operations. The iterations to sum up both arrays and create the final list from the summed up integers are linear operations as well. Four linear operations combined, results mathematically in O(n * 4) and yet is expressed as **Big** **O(n). **Overall, the runtime still requires a lot of optimization.

Always remember to drop constants from Big O notations. O(4 * n) is expressed as O(n).

### The Optimized Approach

In contrary to the brute force solution, all steps described above are being performed at the same time.

Store the references for the current nodes as well as the carry of the mathematical addition operation and populate the new list **on the fly**.

```
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
// Get a mutable reference to each head of l1 and l2
var currentL1: ListNode? = l1
var currentL2: ListNode? = l2
// Create a reference to a node we're going to append on
var sumList: ListNode? = ListNode(-1)
// And a reference to its head
var head: ListNode? = sumList
// The carry for values > 9
var carry: Int = 0
// While we haven't fully iterated both lists yet...
while currentL1 != nil || currentL2 != nil {
/**
Get a dummy value of 0 for each list
in the niche case that either list
is longer than the other.
*/
var value1: Int = 0
var value2: Int = 0
// Replace with l1's value if it exists
if let l1 = currentL1 {
value1 = l1.val
}
// Same for l2
if let l2 = currentL2 {
value2 = l2.val
}
// Sum up both values and the last carry
let sum: Int = value1 + value2 + carry
// Get the value < 10
let value = sum % 10
// Get the carry if above 10
carry = sum / 10
// Add a node with the new value
sumList?.next = ListNode(value)
// And move the head reference
sumList = sumList?.next
// Move l1 and l2 along as well
currentL1 = currentL1?.next
currentL2 = currentL2?.next
}
// If we still have carry left
if carry > 0 {
/**
Add a node for the carry.
This case could happen on
(9 -> 9) + (1) = (0 -> 0 -> 1)
*/
sumList?.next = ListNode(carry)
}
// Return head.next to lose the -1 dummy head
return head?.next
}
```

As you can see, the optimized solution has a single linear runtime and uses much less space. The brute force solution has a time and space complexity of O(n * 4) which is expressed as O(n), the same overall time and space complexity of the optimized solution.