O(n) in Swift using Recursion


  • 0
    J
    class Solution {
        func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
            var length1 = 0
            var length2 = 0
            var node1 = l1
            var node2 = l2
            while node1 != nil || node2 != nil {
                if node1 != nil {
                    length1 += 1
                }
                if node2 != nil {
                    length2 += 1
                }
                
                node1 = node1?.next
                node2 = node2?.next
            }
            
            let result = addTwoNumbersHelper(l1, l2, length1, length2)!
            
            if result.1 {
                let node = ListNode(1)
                node.next = result.0
                return node
            }
            
            return result.0
        }
        
        func addTwoNumbersHelper(_ l1: ListNode?, _ l2: ListNode?, _ toEnd1: Int, _ toEnd2: Int) -> (ListNode, Bool)? {
            if l1 == nil && l2 == nil {
                return nil
            }
            
            var val = 0
            if let l1 = l1, toEnd1 >= toEnd2 {
                val += l1.val
            }
            if let l2 = l2, toEnd2 >= toEnd1 {
                val += l2.val
            }
            
            var next1 = l1?.next
            var next2 = l2?.next
            var nextEnd1 = toEnd1 - 1
            var nextEnd2 = toEnd2 - 1
            
            if toEnd1 > toEnd2 {
                next2 = l2
                nextEnd2 += 1
            } else if toEnd2 > toEnd1 {
                next1 = l1
                nextEnd1 += 1
            }
            
            if let result = addTwoNumbersHelper(next1, next2, nextEnd1, nextEnd2) {
                if result.1 {
                    val += 1
                }
                
                let node = ListNode(val % 10)
                node.next = result.0
                
                return (node, val >= 10)
            } else {
                return (ListNode(val % 10), val >= 10)
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.