Adding a Node to the Linked List is taking a longer Time when using a reference to the Tail Node

Question

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

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

@dfhwe I have formatted some of the code,let me know if there are any existing changes you want me to make — MANOJ VARMA
– MANOJ VARMA, Commented Jul 17, 2019 at 16:42
For future reference: freecodeformat.com/c-format.php. Also, you are using Java document comments instead of C# comments. — dfhwze
– dfhwze, Commented Jul 17, 2019 at 18:21
@dfhwze Edited the comments as well,didn't notice until it was pointed out,Copied the commented code from the question — MANOJ VARMA
– MANOJ VARMA, Commented Jul 18, 2019 at 1:09
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. — Pieter Witvoet
– Pieter Witvoet, Commented Jul 18, 2019 at 8:33
@PieterWitvoet, Thanks for the Input,I was thinking the same about scalability — MANOJ VARMA
– MANOJ VARMA, Commented Jul 18, 2019 at 10:48

AlanT · Accepted Answer · 2019-07-18 07:27:26Z

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
}

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 — MANOJ VARMA
– MANOJ VARMA, Commented Jul 18, 2019 at 10:45
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 — AlanT
– AlanT, Commented Jul 18, 2019 at 13:09

Stack Exchange Network

Adding a Node to the Linked List is taking a longer Time when using a reference to the Tail Node

Question:

Solution 1:

Solution 2:

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Adding a Node to the Linked List is taking a longer Time when using a reference to the Tail Node

Question:

Solution 1:

Solution 2:

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions