C++ O(1) space except output list O(n) time, without modifying input list


  • 0
    H

    @jade86 's idea is very good, but strictly speaking, his implementation still requires O(n) space because he first allocated a temporal list and then deleted it. Inspired by his idea. I re-implemented the code in which only the result list is allocated once. So it is O(1) space except the output list. The time complexity is O(n) and it is easy to read.

     * 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) {
            int n1=0, n2=0, sum=0;
            ListNode *cur1=l1, *cur2= l2, *res=nullptr;
            while(cur1!=nullptr) {cur1=cur1->next;n1++;}  // count the number of digits
            while(cur2!=nullptr) {cur2=cur2->next;n2++;}
            cur1=l1;cur2=l2;
            while(n1>0 && n2>0)
            {
                sum=0;
                if(n1>=n2){sum+=cur1->val;cur1=cur1->next;n1--;}
                if(n2>n1) {sum+=cur2->val;cur2=cur2->next;n2--;}
                res=addToFront(sum,res);        // calculate the sum and put the result in a reverse order.
            }
            int carry=0;
            cur1=res;
            
            while(cur1!=nullptr)               // propagate down the carries
            {
                sum=cur1->val+carry;
                cur1->val=sum%10;
                carry=sum/10;
                cur1=cur1->next;
            }
            res=reverseList(res);           // reverse the result list
            if(carry!=0)
                res=addToFront(carry, res);   // add 1 to the front of list if needed
            return res;
            
        }
        ListNode* reverseList(ListNode* head) {
            ListNode* temp, * reshead=NULL;
            while(head!=NULL)
            {
                temp=head;
                head=head->next;
                temp->next=reshead;
                reshead=temp;
            }
            return reshead;
        }
        ListNode* addToFront(int val, ListNode* head)
        {
            ListNode* temp=new ListNode(val);
            temp->next=head;
            return temp;
        }
    };```

Log in to reply
 

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