LeetCode: Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

---

The idea is adding digit by digit with the use of carry_on bit. Note that after adding two linked list, we need to check if there are still remaining elements in either list.

C++ Code:

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL){}
};

/*
 *func: add_two_numbers
 *goal: add two non-negtive numbers represented by link list
 *@param l1: the head of linked list 1
 *@param l2: the head of linked list 2
 *return: the head of the new linked list representing the sum
 */
/*
 *Just Add one bit by one bit
 *Time complexity: O(m+n), space complexity: O(m+n) where m is the
 *length of l1 and n is the length of l2
 */
ListNode* add_two_numbers(ListNode *l1, ListNode *l2){
    //iterator for l1 and l2
    ListNode *iter1 = l1, *iter2 = l2;
    
    //head of final result and iterator of final result
    ListNode *head = NULL, *iter_ret = new ListNode(0);
    
    //carry on variable
    bool carry_on = false;
    
    while(iter1 != NULL && iter2!= NULL){
        int sum = iter1->val + iter2->val + carry_on;
        
        //Set carry_on bit
        carry_on = sum >= 10 ? true : false;
        
        //Create new node
        iter_ret->next = new ListNode(sum >= 10 ? sum-10 : sum);
        
        //Set head pointer
        if(head == NULL){
            head = iter_ret->next;
        }
        
        //Go to the next one
        iter_ret = iter_ret->next;
        iter1 = iter1->next;
        iter2 = iter2->next;
    }
    
    //Check tail of iter1
    while(iter1 != NULL){
        int sum = iter1->val + carry_on;
        
        //Set carry_on bit
        carry_on = sum >= 10 ? true : false;
        
        //Create new node
        iter_ret->next = new ListNode(sum >= 10 ? sum-10 : sum);
        
        //Set head pointer
        if(head == NULL){
            head = iter_ret->next;
        }
        
        //Go to the next one
        iter_ret = iter_ret->next;
        iter1 = iter1->next;
    }
    
    //Check tail of iter2
    while(iter2 != NULL){
        int sum = iter2->val + carry_on;
        
        //Set carry_on bit
        carry_on = sum >= 10 ? true : false;
        
        //Create new node
        iter_ret->next = new ListNode(sum >= 10 ? sum-10 : sum);
        
        //Set head pointer
        if(head == NULL){
            head = iter_ret->next;
        }
        
        //Go to the next one
        iter_ret = iter_ret->next;
        iter2 = iter2->next;
    }
    
    //Check carry on
    if(carry_on){
        iter_ret->next = new ListNode(1);
    }
    
    return head;
}

Python Code:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

#func: add two numbers represented by linked list
#@param l1: the head of l1
#@param l2: the head of l2
#@return: the head of the final result
#Complexity: time O(m+n), space O(m+n)
def add_two_numbers(l1, l2):
    #iterator for l1 and l2
    iter1 = l1
    iter2 = l2

    #head of final result and iterator of final result
    iter_ret = ListNode(0)
    head = None

    #carry_on digit
    carry_on = False

    while iter1 and iter2:
        #Compute sum
        sum = iter1.val + iter2.val + carry_on
        #Set carry_on bit
        carry_on = True if sum >= 10 else False
        #Create new node
        iter_ret.next = ListNode(sum - 10 if sum >= 10 else sum)

        #Set head
        if not head:
            head = iter_ret.next

        #Go to the next one
        iter_ret = iter_ret.next
        iter1 = iter1.next
        iter2 = iter2.next

    #Check tail of iter1
    while iter1:
        #Compute sum
        sum = iter1.val + carry_on
        #Set carry_on bit
        carry_on = True if sum >= 10 else False
        #Create new node
        iter_ret.next = ListNode(sum - 10 if sum >= 10 else sum)

        #Set head
        if not head:
            head = iter_ret.next

        #Go to the next one
        iter_ret = iter_ret.next
        iter1 = iter1.next

    #Check tail of iter2
    while iter2:
        #Compute sum
        sum = iter2.val + carry_on
        #Set carry_on bit
        carry_on = True if sum >= 10 else False
        #Create new node
        iter_ret.next = ListNode(sum - 10 if sum >= 10 else sum)

        #Set head
        if not head:
            head = iter_ret.next
            
        #Go to the next one
        iter_ret = iter_ret.next
        iter2 = iter2.next

    #Check carry_on bit
    if carry_on:
        iter_ret.next = ListNode(1)

    return head