javalinked-listsingly-linked-list

Stuck on the Case 3 of Leetcode "Add two Sums"


Currently I'm doing a daily Leetcode streak and I have no idea why my code couldn't pass the case 3. (I have done modifying and tracing the code, but maybe I'm a bit dumb and couldn't spot the error.) Hopefully this is not any silly dumbo mistake, thanks for helping!

Refer to this leetcode question.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {
        }
 *     ListNode(int val) {
            this.val = val; 
        }

 *     ListNode(int val, ListNode next) { 
            this.val = val; 
            this.next = next; 
    }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        // Making an empty LinkList to store answers
        ListNode answer = new ListNode();

        // A pointer the transverse the answer
        ListNode current = answer;

        // Dont forget carries
        int carry = 0;

        // Setting up global variable
        int l1_value, l2_value;

        // If carry = 0 means Answer is DONE!
        while(l1 != null || l2 != null || carry != 0) {
            // If l1 -> null, then 0
            if (l1 != null) {
                l1_value = l1.val;              // Directly get val if it is public
            } else l1_value = 0;

            if (l2 != null) {
                l2_value = l2.val;
            } else l2_value = 0;

            // DONT FORGET ABOUT CARRY
            int total = l1_value + l2_value + carry;
            int remainder = total % 10;


            current.next = new ListNode(remainder, current.next);
            carry = total / 10;

            // Transverse to next, else null
            if (l1 != null && l1.next != null) {
                l1 = l1.next;
            } else l1 = null;

            
            // Error occurs because at some point this would become NULL, causes the NullPointerException
            if (l2 != null && l2.next != null) {
                l2 = l2.next;
            } else l2 = null;
            
            // I think the extra 0s, 1s are from the CARRY here [Added if condition]
            // Error still occur but much better, added [carry != 0], T1/2 done! but T3 zzzz
            if (l1 == null && l2 == null && carry != 0) {
                current.next = new ListNode(carry, current.next);
            }
            current = current.next;
        }
        return answer.next;
    }
}

The questions and answers:

l1 = [9,9,9,9,9,9,9]
l2 = [9,9,9,9]

expected output = [8,9,9,9,0,0,0,1]
my output = [8,9,9,9,0,0,1,1,0]


Solution

  • You basically solved it yourself already. The problem is exactly where you expected it:

            // I think the extra 0s, 1s are from the CARRY here [Added if condition]
            // Error still occur but much better, added [carry != 0], T1/2 done! but T3 zzzz
            if (l1 == null && l2 == null && carry != 0) {
                current.next = new ListNode(carry, current.next);
            }
    

    This is just redundant. You already added the carry before:

    int total = l1_value + l2_value + carry;
    

    So total is always != 0 if you have a carry. Thus remainder is != 0 an thus, this ListNode is enough:

    current.next = new ListNode(remainder, current.next);
    

    Just remove the extra creation of the ListNode and the result will be as expected.

    My full code:

    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
            // Making an empty LinkList to store answers
            ListNode answer = new ListNode();
    
            // A pointer the transverse the answer
            ListNode current = answer;
    
            // Dont forget carries
            int carry = 0;
    
            // Setting up global variable
            int l1_value, l2_value;
    
            // If carry = 0 means Answer is DONE!
            while (l1 != null || l2 != null || carry != 0) {
                // If l1 -> null, then 0
                if (l1 != null) {
                    l1_value = l1.val;              // Directly get val if it is public
                } else l1_value = 0;
    
                if (l2 != null) {
                    l2_value = l2.val;
                } else l2_value = 0;
    
                // DONT FORGET ABOUT CARRY
                int total = l1_value + l2_value + carry;
                int remainder = total % 10;
    
    
                current.next = new ListNode(remainder, current.next);
                carry = total / 10;
    
                // Transverse to next, else null
                if (l1 != null && l1.next != null) {
                    l1 = l1.next;
                } else l1 = null;
    
    
                // Error occurs because at some point this would become NULL, causes the NullPointerException
                if (l2 != null && l2.next != null) {
                    l2 = l2.next;
                } else l2 = null;
                
                current = current.next;
            }
            return answer.next;
        }
    
        public static void main(String[] args) {
            var l1 = new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9)))))));
            var l2 = new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9))));
    
    
            ListNode result = new Solution().addTwoNumbers(l1, l2);
    
            print(result);
        }
    
        private static void print(ListNode result) {
            System.out.print(result.val);
    
            if (result.next != null) {
                print(result.next);
            }
        }
    }
    
    class ListNode {
        int val;
        ListNode next;
    
        ListNode() {
        }
    
        ListNode(int val) {
            this.val = val;
        }
    
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    

    Gives me the result: 89990001