0
\$\begingroup\$

I am trying to add two numbers in the form of linked List and return their result in a Linked List as given in https://leetcode.com/problems/add-two-numbers/

Question:

You are given two non-empty linked lists representing two non-negative integers. 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.

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

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807, my solution has solved all the test cases but after refactoring, it is taking longer than the original code

Solution 1:

//public class ListNode
//{
//    public int val;
//    public ListNode next;
//    public ListNode(int x) { val = x; }
//};

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3 = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int first = 0,
            second = 0;
            if (l1 != null) {
                first = l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                second = l2.val;
                l2 = l2.next;
            }
            int Digit = first + second;
            if (carry != 0) {
                Digit = Digit + carry;
                carry = 0;
            }
            if (Digit > 9) {
                carry = Digit / 10;
                Digit = Digit % 10;
            }
            AddLastNode(Digit, ref l3);
        }
        if (carry != 0) {
            AddLastNode(carry, ref l3);
            carry = 0;
        }
        return l3;
    }

    /// In here I am looping through the Linked List every time,to find the tail node 
    private static void AddLastNode(int Digit, ref ListNode l3) {
        if (l3 != null) {
            AddLastNode(Digit, ref l3.next);
        }
        else {
            l3 = new ListNode(Digit);
        }
    }
}

So to avoid looping through all the Nodes,in the below solution I am using a reference for the Tail Node

Solution 2:

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3 = null;
        ListNode tailNode = null;
        int remainder = 0;
        while (l1 != null || l2 != null) {
            int sum = 0;
            if (l1 != null) {
                sum = l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            if (remainder != 0) {
                sum += remainder;
            }
            if (sum > 9) {
                remainder = sum / 10;
                sum = sum % 10;
            }
            else {
                remainder = 0;
            }
            ///In here I am using tailNode has reference for adding new node to the end of Linked List
            if (tailNode == null) {
                l3 = new ListNode(sum);
                tailNode = l3;
            }
            else {
                tailNode.next = new ListNode(sum);
                tailNode = tailNode.next;
            }
        }
        if (remainder != 0) {
            tailNode.next = new ListNode(remainder);
        }
        return l3;
    }
}

Since I got a tail node for the end of Linked List instead of going through entire Linked List,I thought the solution 2 will have better performance.But it is still taking more time to execute than the first solution ,Any code changes would be appreciated

enter image description here

Solution 1 is taking 108 ms to execute while Solution 2 is taking 140 ms

\$\endgroup\$
  • \$\begingroup\$ @dfhwe I have formatted some of the code,let me know if there are any existing changes you want me to make \$\endgroup\$ – MANOJ VARMA Jul 17 at 16:42
  • \$\begingroup\$ For future reference: freecodeformat.com/c-format.php. Also, you are using Java document comments instead of C# comments. \$\endgroup\$ – dfhwze Jul 17 at 18:21
  • \$\begingroup\$ @dfhwze Edited the comments as well,didn't notice until it was pointed out,Copied the commented code from the question \$\endgroup\$ – MANOJ VARMA Jul 18 at 1:09
  • \$\begingroup\$ Your first solution uses what's sometimes called a 'Schlemiel the painter's algorithm' - it scales very poorly. Try adding numbers with hundreds and thousands of digits and you'll see. \$\endgroup\$ – Pieter Witvoet Jul 18 at 8:33
  • \$\begingroup\$ @PieterWitvoet, Thanks for the Input,I was thinking the same about scalability \$\endgroup\$ – MANOJ VARMA Jul 18 at 10:48
2
\$\begingroup\$

In terms of the times on LeetCode, they can be dependent upon the server load as much as the code. I tried your code and got a range of times from 100 ms to 136 ms. Holding onto the last node is a better solution than repeatedly trying to find it but on a list of only a few nodes I don't know how much impact it would have.

In terms of the code, this strikes me as a good place to use the Null Condtional Operator (?.). We can get around the repeated null check on the tailnode by using a dummy head for the return list.

public ListNode AddTwoNumbers(ListNode l1, ListNode l2) 
{
    ListNode l3 = new ListNode(-1);  // dummy head
    ListNode tailNode = l3;
    int remainder = 0;
    while (l1 != null || l2 != null) {

        var sum = (l1?.val ?? 0) + 
                  (l2?.val ?? 0) + 
                  remainder;
        l1 = l1?.next;
        l2 = l2?.next;

        if (sum > 9) {
            remainder = sum / 10;
            sum = sum % 10;
        }
        else {
            remainder = 0;
        }
       tailNode.next = new ListNode(sum);
       tailNode = tailNode.next;

    }
    if (remainder != 0) {
        tailNode.next = new ListNode(remainder);
    }
    return l3.next; // skip the dummy head when returning
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the code,if we change the requirements to allow empty or null Linked List as Input,how can we handle that since we will be returning null ListNode \$\endgroup\$ – MANOJ VARMA Jul 18 at 10:45
  • \$\begingroup\$ As far as I can see the existing code allows for null inputs as long as we are happy that two null inputs result in a null being returned. If not, then we can check for two nulls and return whatever we want the answer to be. Either one being null is no different than dealing with numbers of different lengths. Not sure what you mean by an empty input - as far as i can see it can either be null or contains a value, there is no 'empty' list \$\endgroup\$ – AlanT Jul 18 at 13:09
  • \$\begingroup\$ ,Thank you for the input \$\endgroup\$ – MANOJ VARMA Jul 18 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.