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.