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.

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.