Add two numbers which are stored as in reversed linked list form

Question

I'm given two non-empty linked lists representing two non-negative integers. Digits are stored in reverse order and each of nodes contain a single digit. The task is adding two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807

There are several solutions for this problem. I'm trying to solve it by converting linked-list formed digits into numbers. I already did convert the lists to numbers but my problem starts here. You are given a linked-list definition and you can not break it. You don't have a default(empty) constructor in this definition. I am not able to reverse my integer sum into linked-list form yet. Here is my code:

public class ListNode {    //given linked -list definition. Should not be manipulated.
     int val;
      ListNode next;
     ListNode(int x) { val = x; }
}

import java.util.*;
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       int num1 = getNumber(l1);
        int num2 = getNumber(l2);
        int sum = num1 + num2;
        return ??  //some how I should return a LinkedList where my sum is converted into it
    }



//getNumber converts given linked-lists into integers 
    public int getNumber(ListNode head) {
       ListNode tmp = head;
    int number = 0;
    int pass = 0;
    while(tmp != null) {
        number += tmp.val * Math.pow(10, pass) ;
        tmp = tmp.next;
        pass++;
    }
    return number;
}

user_3199595 · Answer

You need to create a whole new list.

Start by creating a new head node. What should it contain? The last digit of the sum, right? So get the last digit of sum: int lastDigit = sum %10 and put it into a new link: new ListNode(lastDigit).

Then do it for the next digit, and the next one, until sum == 0. Remember to link ListNode to each other after creating each one. It would probably be something like prevNode.next = new ListNode(lastDigit)

user_641955 · Answer

The very purpose of this exercise is to use the given data structure to perform the computation. You are not supposed to convert the linked list to an int. Why, the values might not fit within the limits of an int. Using a linked list you could perform the operation on numbers with thousands of digits.

Here's an incomplete sketch that should help you, without spoiling the exercise.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    return addTwoNumbers(l1, l2, 0);
}

private ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry) {
    // TODO: know when to stop!
    // ex: if you have reached the end of l1, then apply carry to l2, if needed, and return
    // ex: if you have reached the end of l2, then apply carry to l1, if needed, and return

    int val = l1.val + l2.val + carry;
    ListNode node = new ListNode(val % 10);
    node.next = addTwoNumbers(l1.next, l2.next, val / 10);
    return node;
}

private ListNode addOne(ListNode l1) {
    // TODO
}

Add two numbers which are stored as in reversed linked list form

2 Answers