Problem Description

You are given two non-empty linked lists, l1 and l2, where each represents a non-negative integer.

The digits are stored in reverse order, e.g. the number 321 is represented as 1 -> 2 -> 3 -> in the linked list.

Each of the nodes contains a single digit. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Return the sum of the two numbers as a linked list.

Example 1:

Input: l1 = [1,2,3], l2 = [4,5,6]
Output: [5,7,9]
Explanation: 321 + 654 = 975.

Example 2:

Input: l1 = [9], l2 = [9]
Output: [8,1]

Constraints:

• 1 <= l1.length, l2.length <= 100
• 0 <= Node.val <= 9

Approach

The current code implements a string-conversion approach:

1. Traverse l1 and construct a string containing its digits reversed (representing the integer).
2. Traverse l2 and perform the same reversal by prepending each digit to a string.
3. Parse both strings into Integer types n1 and n2, and add them to get n3.
4. Construct a new linked list by extracting the rightmost digits of n3 one by one using modulo (%) and division (/).
5. Return the newly created linked list.

Note: For linked lists containing 100 nodes, string concatenation and parsing into standard integers may cause overflow issues (an Integer cannot hold up to 100 digits). An optimal approach adds digits node by node directly using a carry pointer without type conversion.

Solution

/**
 * 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) {
        String str1 = "";
        String str2 = "";
        while(l1!=null){
            str1 = (l1.val+"")+str1;
            l1 = l1.next;
        }
        while(l2!=null){
            str2 = (l2.val+"")+str2;
            l2 = l2.next;
        }
        Integer n1 = Integer.parseInt(str1);
        Integer n2 = Integer.parseInt(str2);
        Integer n3 = n1+n2;
        ListNode newList = new ListNode(0);
        ListNode temp = newList;
        if(n3==0){
            return newList;
        }
        while(n3>0){
            temp.next = new ListNode(n3%10);
            n3 = n3/10;
            temp = temp.next;
        }

        return newList.next;
    }
}