Hallo dames en heren, Leo hier. Today we will explore the Leetcode linked list problem called Add Two Numbers in Swift.

The problem involves we apply the adding operations to two linked lists. It is not a complex problem but you should know how to traverse a linked list to solve it. Keeping the actual reference to the list and making operations on each node is crucial to anyone who wants to solve linked list problems.

With that in mind, we will tackle this difficult medium problem today

Let’s code! But first…

Painting of The Day

The art today is an 1939 called Ground Swell by Edward Hopper. 

Edward Hopper was born into a middle-class family in NY a hub of transport and industry at the time. The boy was already serious about his artistic ambitions at the age of 10 when he started to sign and date his drawings. In 1905, Hopper began working as an illustrator for a New York City advertising agency. He never really liked illustrating and longed for the freedom to paint from his imagination. Unfortunately, success was slow in coming and he was forced to earn his living as an illustrator for nearly 20 more years until his painting career took off.

I chose this painting because today we will talk about math and believe it or not, sailing involves a lot of math. 

The Problem – Add Two Numbers in Swift

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

The problem we will solve today is Leetcode number 2 problem. That involves you adding all the values from two linked lists that look like the mathematical addition operation.

Observe the image below: 

How would you start to tackle this problem? Would you transform to int both of the lists? But what if the number couldn’t be handled by an Integer?

Solution 

First, let’s write down the pseudocode for solving this problem. Step by step you can observe that actually are a lot of simple steps combined.

1. The first value from each of the linked lists 
2. Sum them creating the current sum
3. Check if you need to add one to this current sum from past sums 
4. Check if the current sum is bigger than 9 if yes, mark that you need to add one to the next number and also get the module by 10 of that number
5. Add this value to the response linked list
6. Get the next values for each of the linked lists 
7. Repeat steps 2 to 6 until one or both linked lists are empty
8. If one of the linked lists is not fully traversed, traverse using steps 1 to 6 until it finishes
9. Return the response linked list.

That’s it! If you pay attention are a lot of steps but each of them is not complex. 

Now check the Swift solution below: 

class Solution {

    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {

        var tempL1 = l1 // this is necessary to manipulate since l1 and l2 are constants by default (let)
        var tempL2 = l2 // this is necessary to manipulate since l1 and l2 are constants by default (let)
        var result: ListNode? = nil // the pointer for the first node in the solution
        var currentResult: ListNode? = nil // the pointer to the current node of the solution
        var shouldAddOne = false // a control variable to check if we need to add one to the current adding operation
        
        while tempL1 != nil && tempL2 != nil { // traverse both until one or both are empty
            let valueL1 = tempL1!.val
            let valueL2 = tempL2!.val
            var resultVal = valueL1 + valueL2
            
            if shouldAddOne { // add one to the current result if we need
                resultVal += 1
                shouldAddOne = false
            }
            
            if resultVal > 9 { // check if the result is bigger than 9 so we can set shouldAddOne to true and module the result by 10
                shouldAddOne = true
                resultVal = resultVal % 10
            }
            
            if result == nil { // if is the first time, we create a new result and add it to the result val and point the current to that
                result = ListNode(resultVal)
                currentResult = result
            } else { // we just create a new node to the current result list and change the pointer to the next position
                currentResult?.next = ListNode(resultVal)
                currentResult = currentResult?.next
            }
            
            tempL1 = tempL1?.next // traverse both lists
            tempL2 = tempL2?.next // traverse both lists
        }
                
        while tempL1 != nil { // if one of the lists are not empty we do the algorithm above but with just one list
            addValuesFrom(list:&tempL1, &shouldAddOne, &currentResult)
        }
        
        while tempL2 != nil { // if one of the lists are not empty we do the algorithm above but with just one list
            addValuesFrom(list:&tempL2, &shouldAddOne, &currentResult)
        }
        
        if shouldAddOne { // in the end we might need to add one to the final result so we need to check that
            currentResult?.next = ListNode(1)
        }
        
        return result
    }

    private func addValuesFrom(list: inout ListNode?, _ shouldAddOne: inout Bool, _ currentResult: inout ListNode?) {
        let valueL2 = list!.val
        var resultVal = valueL2
        
        if shouldAddOne {
            resultVal += 1
            shouldAddOne = false
        }
        
        if resultVal > 9 {
            shouldAddOne = true
            resultVal = resultVal % 10
        }
        
        currentResult?.next = ListNode(resultVal)
        currentResult = currentResult?.next
        
        list = list?.next
    }
}

And that’s it!

Time and Space Complexity – The Big O Notation

The Time Complexity is O(N) where N is the linked list with the bigger length. Because we need to traverse each at least one time each value this time complexity can not be reduced.

The Space Complexity is also O(N) where N is the linked list with the bigger length. We are creating a new linked list with the result of the addition of the two input lists. Maybe you could create an algorithm that uses one of them as a result? That would save a lot of memory making it O(1).

Continue Studying

String manipulation in Swift is not easy, that’s why you should always practice with problems that involve Strings. One of the most classics is this solution for the palindrome problem, checking that article you will solve a special kind of palindrome where both words end up with the same character.

Using languages feature can be good leverage for your code interviews, that’s why I wrote this article where we study how to solve an algorithm problem with just functional programming Swift language features. Functional programming can be hard, but once you get a grasp on it, you will start to see things differently.

Summary – Add Two Numbers in Swift

The problem today involved a little bit of math and a lot of linked lists traversal. The big thing about this algorithm is just kept controlling when you should add or not 1 to the current sum. Traverse linked lists are a very important skill to have when solving algorithms problems and you should not overlook those.

Remember that studying linked lists also helps your brain to deal with nodes and references that is exactly what you do when you do graph problems.

Fellow developers, that’s all. I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or just leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.

Thanks for the reading and… That’s all folks.

Image Credit: Wikiart