Πρόβλημα Leetcode με ListNode

[Asevastos]

Καλησπέρα, έχω αρχίσει να ασχολούμαι από σήμερα με προβλήματα από Leetcode. Θα ήθελα μια βοήθεια με ένα πρόβλημα της κατηγορίας "Medium". Η εκφώνηση είναι η εξής:

Αναφορά σε κείμενο

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.

Έχω φτάσει στο τέλος, λοιπόν, όπου πρέπει να επιστρέψω στη συνάρτηση τη λίστα με το σωστό output και εδώ και πόση ώρα κάνω λάθη και δε μπορώ να χτίσω σωστά τη τελική λίστα (μου βγάζει NullPointerException). Η λύση είναι λίγο ωμή και μπακάλικη αλλά σε αρχική φάση προσπαθώ να λύνω απλώς τα προβλήματα, η βελτιστοποίηση αργότερα. Η λύση είναι η εξής:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int count=0;
        ListNode l1Temp = l1;
        while (l1Temp.next!=null){
            count++;
            l1Temp = l1Temp.next;
        }
        count++; //Ο αριθμός των nodes και των δύο αρχικών λιστών
        int[] arr1 = new int[count];
        int[] arr2 = new int[count];
        for (int i=count-1;i>=0;i--){
            arr1[i] = l1.val;
            arr2[i] = l2.val; //Περνάω σε arrays τις τιμές των λιστών ανάποδα
            l1 = l1.next;
            l2 = l2.next;
        }
        int k = 0;
        int l = 0;
        for (int i=0;i<count;i++){
             k = 10*k + arr1[i];
             l = 10*l + arr2[i]; //Συνθέτω σε ενιαίους αριθμούς, δλδ κάνω το 2 4 3 ->243, το ίδιο και για το 5 6 4
        }
        int m = k+l; //προσθέτω τους αριθμούς
        int j = 0;
        int[] digits = new int[count];
        while (m>0){
            digits[j] = m%10; //σπάω τον ενιαίο αριθμό 807 σε 8 0 7
            m = m/10; 
            j++;
        }
        ListNode finalt = new ListNode(); //δημιουργώ νέο κόμβο για να προσθέσω τα ψηφία
        finalt.val = digits[0];
        return finalt;
    }
}

Όπως βλέπετε δεν είναι τελειωμένη στο τέλος αφού ψάχνω τον σωστό τρόπο για να προσθέτω νέα nodes και να αναθέτω σε αυτά τις τιμές. Προσπαθούσα να χρησιμοποιήσω for και να προσθέτω στους νέους κόμβους finalt.next.val τις νέες τιμές αλλά κάτι έκανα λάθος και έπαιρνα NullPointerExc. Καμία βοήθεια για να καταλάβω επιτέλους πως θα γίνει;

[kaliakman]

Αυτό που κάνεις ουσιαστικά δεν είναι το πρόβλημα. Πρεπει να δημιουργεις την λίστα δυναμικά όπως προχωρας ψηφίο ψηφίο και όχι να κάνεις την λίστα αριθμό, πρόσθεση και μετά ξανά λίστα.

 

Το πρόβλημα σου ποιο είναι; Έχεις ξαναχρησιμοποιήσει java? Πρέπει για κάθε κόμβο που φτιάχνεις να κάνεις new.

 

Θα πρότεινα να ξεκινήσεις από easy για να εξοικειωθείς με τέτοιου είδους προβλήματα και θα βελτιωθείς γρήγορα.

[Asevastos]

Java τώρα μαθαίνω και παράλληλα θέλω να λύνω προβλήματα. Είχα κάνει παλιότερα 1 μεγάλο project για τη σχολή αλλά πέρασε καιρός από τότε. Εν τέλει κατάφερα να βρω τη λύση χθες κάνοντας αυτό που είπες δημιουργώντας νέα nodes με new αλλά δεν περνούσε όλα τα test cases οπότε έκανα και άλλες αλλαγές. Ισχύει ότι το approach μου δεν είναι καλό αλλά με μπερδεύει λίγο αυτή η δομή και λογική των λιστών αλλά και των δέντρων όπως τα παρέχει το Leetcode (που είναι και το σωστό). 

[kaliakman]

Για αυτόν ακριβώς τον λόγο πρέπει να ξεκινήσεις από τα easy. Έτσι μόνο κακό κάνεις. Επίσης καλύτερα είναι πρώτα να ξεκινήσεις ένα βιβλίο όπως το cracking the coding interview που είναι δομημενο παρα να λύνεις προβλήματα αφού έχεις θέμα με απλές δομες. Καλή επιτυχία! 

[albNik]

Μην προσπαθεις να φτιαξεις το αριθμο απο τη λιστα αφου το αποτελεσμα θα ειναι παλι λιστα. Επίσης μπορει να εχουν πολλα ψηφια (π.χ. 1000) που να μην χωράνε σε integer

κανε iteration καθε ψηφιο
π.χ. για το παρακατω input:

8->7->6
+
4->5->2->7

εχουμε:

8+4=2 (κρατουμενο 1)
1+7+5=3 (κρατουμενο 1)
1+6+2=9 
7+0=7

αποτελεσμα 2->3->9->7