Add two numbers stored in reverse order in linked lists-CodePudding

I'm trying to solve the following problem:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in forward order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:
2 --> 4 --> 3
5 --> 6 --> 4
8 --> 0 --> 7

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]
Explanation: 243   564 = 807

The linked list is a collection of ListNode objects where each object points to the next one. The ListNode class is the following:

// 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; }
}

I've tried the follwing solution with a recursive approach

import java.util.HashMap;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        head.val = generateSumList(l1.next, l2.next, head.next);
        return head;
    }


    public int generateSumList(ListNode l1, ListNode l2, ListNode res) {
        
        int rest, sum;

        if (l1.next == null && l2.next != null) {
            return generateSumList(l1, l2.next, res.next);
        }

        if (l1.next != null && l1.next == null) {
            return generateSumList(l1.next, l2, res.next);
        }

        if (l1.next == null && l2.next == null) {
            sum = l1.val   l2.val;
            if (sum > 9) {
                ListNode n = new ListNode(sum % 10, null);
                res = n;
                return 1;
            }
            else {
                ListNode n = new ListNode(sum, null);
                res = n;
                return 0;
            }
        }

        rest = generateSumList(l1.next, l2.next, res.next);
        sum = l1.val   l2.val   rest;
        if (sum > 9) {
            res.val = sum % 10;
            return 1;
        }
        else {
            res.val = sum;
            return 0;
        }
    }
}

I'm having the follwing error msg at runtime and I cannot understand why.

java.lang.NullPointerException: Cannot read field "next" because "<parameter1>" is null
  at line 27, Solution.generateSumList
  at line 17, Solution.addTwoNumbers
  at line 54, __DriverSolution__.__helper__
  at line 87, __Driver__.main

Why am I having the NPE? Are my approach to the problem and my intuition on how to solve it correct?

CodePudding user response：

Why am I having the NPE?

The node you assign to head has a next member that is null. This null is passed as last argument to generateSumList, so that res is null. When neither l1.next nor l2.next is null the following line is executed and produces the NPE as it evaluates res.next:

    rest = generateSumList(l1.next, l2.next, res.next);

Are my approach to the problem and my intuition on how to solve it correct?

No, it cannot work like that. For one, if the two lists have an unequal length, you cannot hope to align the two corresponding digits from both lists. Although you get the last two digits aligned and added together, eventually, sum = l1.val l2.val rest; will get executed, but those two nodes are equally positioned when counting from the left, but should be aligned by their distance from the right. In short, when the lists have an unequal length, this sum is summing up unrelated digits.

To achieve a correct alignment of the nodes, you would better first reverse both lists, so the least significant digits come first, and are naturally aligned as you move forward.