C solution (20ms)


  • 2
    I
    struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
    {
        struct ListNode* res,*pt,*node;
        int j = 0,temp = 0;
        res = (struct ListNode*) malloc(sizeof(struct ListNode));
        res->next = NULL;
        pt = res;
        while (l1 != NULL || l2 != NULL || j!=0)
        {
            node = (struct ListNode*) malloc(sizeof(struct ListNode));
            temp = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + j;
            node->val = temp%10;
            j = temp/10;
            node->next = NULL;
            pt->next = node;
            pt = node;
            l1 = l1 ? l1->next : l1;
            l2 = l2 ? l2->next : l2;
        }
        pt = res->next;
        free(res);
        return pt;
    }
    

    Hope for some comments.


  • 0
    A

    @i4never nice code


  • 0
    I

    @Anbug Thanks!


  • 0
    S

    @i4never nice, notice code style


  • 0
    V
    node->val = temp%10;
            j = temp/10;
    

    can anyone tell me how this snippet is get optimized by compiler?


  • 0
    V

    I was trying to optimize timing manually for your solution, but had no luck, it's almost your time all the time.
    So solution happened to be no better than your, even when your code has million allocations, % and /.
    I guess it's cache, but how? :-) It's really awesome.

    struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
    {
        struct ListNode* head,*pt,*node;
        int j = 0,temp = 0;
        int b;
        head = l1;
        
        while (l1)
        {
            node = l1;
            b = l1->val;
            
            // j + b
            temp = ((j ^ b ^ ((j&b)<<1)) ^ (((j ^ b)&((j&b)<<1))<<1)) ^ (((j ^ b ^ ((j&b)<<1)) & (((j ^ b)&((j&b)<<1))<<1)) << 1);
            l1 = l1->next;
            if (l2){
                b = l2->val;
                l2 = l2->next;
                // temp + b
                temp = ((temp ^ b ^ ((temp&b)<<1)) ^ (((temp ^ b)&((temp&b)<<1))<<1)) ^ (((temp ^ b ^ ((temp&b)<<1)) & (((temp ^ b)&((temp&b)<<1))<<1)) << 1) ^ (((temp ^ b ^ ((temp&b)<<1)) ^ (((temp ^ b)&((temp&b)<<1))<<1)) & (((temp ^ b ^ ((temp&b)<<1)) & (((temp ^ b)&((temp&b)<<1))<<1)) << 1)) << 1;
            }
            
            // j >= 10
            j = (temp&16) >> 4 | (((temp&8) >> 3) & (((temp&4) >> 2) | ((temp&2) >> 1)));
            
            // b = j ? 10 : 0
            b = ((j&1)<<2 | (j&1)) << 1;
    
            // temp-10
            node->val = ~((~temp ^ b ^ ((~temp&b)<<1)) ^ (((~temp ^ b)&((~temp&b)<<1))<<1));
            
            pt = node;
        }
        
        
        if (l2) {
            pt->next = l2;
        }
        while (l2)
        {
            node = l2;
            
            b = l2->val;
            
            l2 = l2->next;
            
            // j + b
            temp = ((j ^ b ^ ((j&b)<<1)) ^ (((j ^ b)&((j&b)<<1))<<1)) ^ (((j ^ b ^ ((j&b)<<1)) & (((j ^ b)&((j&b)<<1))<<1)) << 1);
            
            // j >= 10
            j = (temp&16) >> 4 | (((temp&8) >> 3) & (((temp&4) >> 2) | ((temp&2) >> 1)));
            
            // b = j ? 10 : 0
            b = ((j&1)<<2 | (j&1)) << 1;
    
            // temp-10
            node->val = ~((~temp ^ b ^ ((~temp&b)<<1)) ^ (((~temp ^ b)&((~temp&b)<<1))<<1));
            
            pt = node;
    
        }
        
        // j == 0 or j == 1
        if (j)
        {
            node = (struct ListNode*) malloc(sizeof(struct ListNode));
    
            node->val = 1;
            node->next = NULL;
            pt->next = node;
        }  
    
        return head;
    }
    

Log in to reply
 

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