445. Add Two Numbers II--Medium

墨蓝 2023-08-17 15:58 111阅读 0赞

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:  
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

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

1.思考

*  方法1：将更小的链表高位补零，使得两个数长度相同；
 *  方法2：参考讨论中的方法，将list中的数放到stack中，这样就可以从最低位开始相加；
 *  方法3：将链表反转，这样也是从最低位开始相加，该方法和stack方法类似。

2.实现  
Runtime: 23ms(73.74%)  
Memory: 10.3MB(81.48%)

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        //Reference Solution    
        //要想取list最后的元素可以用stack
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){
            stack<int> st1, st2;
            while(l1!=NULL){
                st1.push(l1->val);
                l1 = l1->next;
            }
            while(l2!=NULL){
                st2.push(l2->val);
                l2 = l2->next;
            }
            ListNode* pHead = new ListNode(0);
            int sum = 0;
            while(!st1.empty() || !st2.empty()){
                if(!st1.empty()){
                    sum += st1.top();
                    st1.pop();
                }
                if(!st2.empty()){
                    sum += st2.top();
                    st2.pop();
                }
                ListNode *list = new ListNode(sum/10);
                pHead->val = sum%10;
                list->next = pHead;
                pHead = list;
                sum /= 10;
            }
            if(pHead->val>0)
                return pHead;
            else
                return pHead->next;
        }
        
        
        //My Solution-Right
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            int len1 = 0, len2 = 0;
            ListNode *ls1 = l1, *ls2 = l2;
            while(ls1!=NULL){
                len1++;
                ls1 = ls1->next;
            }
            while(ls2!=NULL){
                len2++;
                ls2 = ls2->next;
            }
            ListNode *list1, *list2, *newList;
            list1 = len1>len2?l1:l2;
            list2 = len1>len2?l2:l1;
            int diff = abs(len1-len2);
            if(diff>0){
                ListNode* lst = new ListNode(0);
                newList = lst;
                diff--;
                while(diff>0){
                    ListNode* l = new ListNode(0);
                    lst->next = l;
                    lst = lst->next;
                    diff--;
                }
                lst->next = list2;
            }
            else{
                newList = list2;
            }
            ListNode *list = addNum(list1, newList);
            if(list->val>=10){
                ListNode* ls = new ListNode(list->val/10);
                list->val %= 10;
                ls->next = list;
                return ls;
            }
            return list;
        }
        
        ListNode* addNum(ListNode* l1, ListNode* l2){
            if(l1->next==NULL && l2->next==NULL){
                ListNode* list = new ListNode(l1->val + l2->val);
                return list;
            }
            ListNode* listNext = addNum(l1->next, l2->next);
            int carry = listNext->val / 10;
            listNext->val %= 10;
            ListNode* list = new ListNode(l1->val + l2->val + carry);
            list->next = listNext;
            return list;
        }
    };

转载于:https://www.cnblogs.com/xuyy-isee/p/11459349.html