Leetcode: Adding two numbers represented in reverse linked list is not working

Question

The following code is not working for the below Input: [2,4,3] [5,6,4] Output: [7,8] Expected: [7,0,8]

Why I am not getting 0? Can anyone please help me.

/**
 * Definition for singly-linked list.
 * 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) {
        return AddTwoNumbersHelper(l1, l2, 0);            
    }


private ListNode AddTwoNumbersHelper(ListNode l1, ListNode l2, int carry) {
    if (l1 == null && l2 == null)
        return null;

    int temp = 0;
    if (l1 != null)
        temp += l1.val;

    if (l2 != null)
        temp += l2.val;

    ListNode result = new ListNode(temp % 10);
    carry = temp / 10;

    l1 = l1.next;
    l2 = l2.next;
    int sum = 0;
    while(l1 != null || l2 != null) {
        sum = carry;

        if (l1 != null)
            sum += l1.val;

        if (l2 != null)
            sum += l2.val;

        carry = sum == 0 ? 0 : sum / 10;
        sum = sum % 10;

        result.next = new ListNode(sum);
        if(l1 != null)
            l1 = l1.next;
        if(l2 != null)
            l2 = l2.next;
    }

    if (carry > 0)
        result.next = new ListNode(carry);

    return result;
}

}

you are overriding result.next all time, you need to keep a reference to first result and then in loop add result = result.next — juvian
– juvian, Commented May 15, 2018 at 20:42
He was not answering rather trying to help me out without directly telling me the answer, which is even better! — Sharif Mamun
– Sharif Mamun, Commented May 19, 2018 at 18:44
If that is the case(which I agree), then it defeats the purpose of SO having sections for posting an answer as well. It could have just enabled comments for every question. — mighty_dev
– mighty_dev, Commented May 19, 2018 at 19:58

prashant · Accepted Answer · 2019-02-25 03:00:27Z

Some flaws with the code:

You don't need the carry parameter in your method unless you're recursing which you're not.
List advancement steps (l = l.next) can be combined with the step in which you're adding the node's value to the temp (sum) variable.
You don't need to write extra code for handling the dangling carry case, you're loop is sufficient for that, just include the condition in the loop.
The bug is because you're continuously updating the next pointer of the head and not building (adding one node) to the linked list in every iteration. You need an extra pointer/variable to do that.
'sum' is a better variable name here than 'temp'.

Here's a slightly modified solution which fixes the above problems:

private ListNode AddTwoNumbersHelper(ListNode l1, ListNode l2) {

    ListNode result = null;
    ListNode tail = null;
    int carry = 0;
    while ((l1 != null) || (l2 != null) || (carry != 0)) {

        int sum = carry;
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        carry = sum/10;
        sum %= 10;
        if (result == null) { // first time
            result = new ListNode(sum);
            tail = result;
        } else {
            tail.next = new ListNode(sum);
            tail = tail.next;
        }
    }
    return result;
}

Collectives™ on Stack Overflow

Leetcode: Adding two numbers represented in reverse linked list is not working

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related