LeetCode 2 Add Two Numbers

Problem Statement

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.
…

Add Two Numbers - LeetCode

Approach

1. Pointer a and b are used to iterate over the linked lists l1 and l2 respectively.
2. A new linked list result is created to store the sum of the two linked lists. It is initialized with a dummy node, that will be discarded.
3. A current pointer is used to add new nodes to the result linked list.
4. A temp variable is used to store the carry value.
5. Iterate until a, b and temp are not empty.
6. Calculate the sum of the current nodes of a and b and the carry value temp.
7. Add the last digit of the sum to the result linked list.
8. Update the temp value with the carry value.
9. Move the pointers a and b to the next nodes.
10. Return the next node of the result linked list.

Solution in Swift

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var a = l1
        var b = l2
        let result = ListNode()
        var current = result
        var temp = 0

        while a != nil || b != nil || temp != 0 {
            temp = (a?.val ?? 0) + (b?.val ?? 0) + temp
            current.next = ListNode(temp % 10)
            current = current.next!
            temp = temp / 10
            a = a?.next
            b = b?.next
        }

        return result.next
    }
}

Complexity

• Time complexity: \(O(n)\)

  where \(n\) is the length of the longer linked list.

• Space complexity: \(O(n)\)

  where \(n\) is the length of the longer linked list.