1. topic

2. answers

2.1 method 1

stay LeetCode 206 - reverse linked list and LeetCode 2 -- sum of two numbers On the basis of this, we first reverse the two linked lists, then find the sum and then reverse them.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        // First, reverse the order of two linked lists
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        
        ListNode *head = new ListNode(0); // Establish sentinel node
        ListNode *temp = head; 

        
        int carry = 0; // Reserved carry
        int sum = 0;
            
        while(l1 || l2)
        {
            if (l1 && l2) // Both lists are not empty
            {
                sum = l1->val + l2->val + carry;
                l1 = l1->next;
                l2 = l2->next;
            }
            else if (l1) // l2 list is empty, only carry and l1 elements are summed
            {
                sum = l1->val + carry;
                l1 = l1->next;
            }
            else // l1 list is empty, only carry and l2 elements are summed
            {
                sum = l2->val + carry;
                l2 = l2->next;
            } 
            
            // Find the sum and carry, and add the sum to the new linked list
            carry = sum >= 10 ? 1 : 0;
            sum = sum % 10;
            head->next = new ListNode(sum);
            head = head->next;
            
            if ( (l1 == NULL || l2 == NULL) && carry == 0 )
            {
                head->next = l1 ? l1 : l2;
                return reverseList(temp->next);
            }

        }
          
    
        if (carry) // If the last digit has carry, carry is the sum of the last digit
        {
            head->next = new ListNode(carry);    
        }
        head->next->next = NULL;
        

        return reverseList(temp->next);
        
    }
    
    ListNode* reverseList(ListNode* head) {
    
        if (head == NULL || head->next == NULL) return head; 
        else 
        { 
            ListNode * p1 = head; 
            ListNode * p2 = p1->next; 
            ListNode * p3 = p2->next; 
            
            while (p2) 
            { 
                p3 = p2->next; p2->next = p1; 
                p1 = p2; 
                p2 = p3; 
            } 
            head->next = NULL; 
            head = p1; 

            return head; 
        }

    }

};

2.2 method 2

First, find the length of the two linked lists, then align the two linked lists, respectively find the sum and carry of each bit according to the corresponding bit, and finally add the sum and carry from the lowest position, that is, the right most, and insert the new node in the head of the linked list.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        int n1 = countListNodeNumber(l1);
        int n2 = countListNodeNumber(l2);
        
        ListNode* long_list = NULL;
        ListNode* short_list = NULL;
        int bigger_n = 0;
        int smaller_n = 0;
        
        if (n1 <= n2)
        {
            long_list = l2;
            short_list = l1;
            bigger_n = n2;
            smaller_n = n1;
        }
        else
        {
            long_list = l1;
            short_list = l2;
            bigger_n = n1;
            smaller_n = n2;   
        }
        int temp = bigger_n - smaller_n + 1;
        int sum_array[bigger_n + 1] = {0};
        int carry_array[bigger_n + 1] = {0};
        int sum = 0;
        int carry = 0;
        
        ListNode* long_temp = long_list;
        ListNode* short_temp = short_list;
        
        for (unsigned int i = 1; i <= bigger_n; i++)
        {
            carry = 0;
            if (i < temp)
            {
                sum = long_temp->val;
            }
            else
            {
                sum = long_temp->val + short_temp->val;
                if (sum >= 10)
                {
                    sum = sum % 10;
                    carry = 1;
                }
                short_temp = short_temp->next;
            }
            sum_array[i] = sum;
            carry_array[i-1] = carry;
            long_temp = long_temp->next;
        }
        
               
        ListNode* new_head = new ListNode(0);
        long_temp = new_head;
        
        for (unsigned int i = bigger_n; i > 0; i--)
        {
            // Insert at the head of the list
            sum = sum_array[i] + carry_array[i];
            if (sum >= 10)
            {
                sum = sum % 10;
                carry_array[i-1] = 1;
            }
            short_temp = new ListNode(sum);
            short_temp->next = long_temp->next;
            long_temp->next = short_temp;
        }
        
        sum = sum_array[0] + carry_array[0];
        if (sum)
        {
            short_temp = new ListNode(sum);
            short_temp->next = long_temp->next;
            long_temp->next = short_temp;
        }
        
        return new_head->next;

    }
    
    int countListNodeNumber(ListNode *head)
    {
        int node_num = 0;
        ListNode* slow = head; 
        ListNode* fast = head; 
        
        while(fast && fast->next) 
        {
            slow = slow->next; 
            fast = fast->next->next; 
            node_num++; 
        } 
        
        if (fast) 
        { 
            node_num = node_num * 2 + 1;
        } 
        else 
        { 
            node_num = node_num * 2; 
        }
        
        return node_num;
    }
    
    
};

2.3 method 3

Put the nodes of two linked lists into two stacks respectively. If both stacks are not empty, take two stack top elements and carry, find the sum and new carry; if one stack is empty, take one stack top element and carry, find the sum and new carry. Then create a new node, insert it in the head of the list, and finally only process the carry of the highest bit.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        stack<ListNode *> stack1;
        stack<ListNode *> stack2;
        
        while (l1)
        {
            stack1.push(l1);
            l1 = l1->next;
        }
        
        while (l2)
        {
            stack2.push(l2);
            l2 = l2->next;
        }
        
        int sum = 0;
        int carry = 0;
        
        ListNode *new_head = new ListNode(0);
        ListNode *temp = NULL;
        
        while (!stack1.empty() && !stack2.empty())
        {
            sum = stack1.top()->val + stack2.top()->val + carry;
            
            if (sum >= 10)
            {
                sum = sum % 10;
                carry = 1;
            }
            else
                carry = 0;
            
            temp = new ListNode(sum);
            temp->next = new_head->next;
            new_head->next = temp; 
            
            stack1.pop();
            stack2.pop();
        }
                

         while (!stack1.empty())
         {
            sum = stack1.top()->val + carry;

            if (sum >= 10)
            {
                sum = sum % 10;
                carry = 1;
            }
            else
                carry = 0;

            temp = new ListNode(sum);
            temp->next = new_head->next;
            new_head->next = temp; 

            stack1.pop();
         }
        

         while (!stack2.empty())
         {
            sum = stack2.top()->val + carry;

            if (sum >= 10)
            {
                sum = sum % 10;
                carry = 1;
            }
            else
                carry = 0;

            temp = new ListNode(sum);
            temp->next = new_head->next;
            new_head->next = temp; 

            stack2.pop();
         }
        
        if (carry)
        {
            temp = new ListNode(carry);
            temp->next = new_head->next;
            new_head->next = temp; 
        }
        
        return new_head->next;
    }   
};

For more highlights, please pay attention to "seniusen"!