0

I'm stuck on this problem:

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list. EXAMPLE Input: (3 -> 1 -> 5), (5 -> 9 -> 2) Output: 8 -> 0 -> 8

The problem is that my result is 8 8 while the result should be 8 0 8. I printed out the sum and it is 8 10 8 so it should work. Any ideas?

Here is my code:

public Node addNumbers(Node number1, Node number2) {

        if(number1 == null && number2 == null)
            return null;

        Node sumOf = null;
        int sum = 0;
        int carry = 0;

        while(number1 != null && number2 != null) {
            sum = number1.data + number2.data + carry;
            System.out.println(sum);
            // update carry for next operation 
            if(sum > 9) 
                carry = 1;
            else 
                carry = 0;

            if(sum > 9) {
                if(sumOf == null) {
                    sumOf = new Node(sum % 10);
                } else {
                    sumOf.next = new Node(sum % 10);
                }

            } else {
                if(sumOf == null) {
                    sumOf = new Node(sum);
                } else {
                    sumOf.next = new Node(sum);
                }

            }

            number1 = number1.next;
            number2 = number2.next;
        }

        return sumOf;
    }

    public void toString(Node node) {
        System.out.println();
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    public static void main(String[] args) {

        AddTwoNumbers add = new AddTwoNumbers();

        number1 = new Node(3);
        number1.next = new Node(1);
        number1.next.next = new Node(5);

        number2  = new Node(5);
        number2.next = new Node(9);
        number2.next.next = new Node(2);

        System.out.println("numbers: ");
        add.toString(number1);
        add.toString(number2);

        System.out.println();
        System.out.println("after adding: ");
        add.toString(add.addNumbers(number1, number2));
    }
}
Improve this question
3
  • 1
    If I was doing this exercise, I would probably write a method to convert each list to a number, perform the addition, and then convert the result back to a linked list. Commented Apr 5, 2016 at 20:15
  • Why not converting the inputs to BigIntegers, add them and convert the result back to a LinkedList? Conversion should be easy with Java8. Commented Apr 5, 2016 at 20:16
  • I was thinking of that initially, but I think the problem wants me to strictly used LinkedList since it's in the LinkedList Ch of Cracking the Coding Interview. Thanks for the suggestions though. Commented Apr 5, 2016 at 21:04

3 Answers 3

Reset to default
1

You only ever set sumOf (if it is null) and sumOf.next (if sumOf is not null). Your resulting list therefore never has more than two elements. You need to track the current tail of your list and append there, instead of always appending to sumOf.

Additionally, you need to handle the cases where one input number has more digits than the other, and where you have non-zero carry after exhausting all the input digits. You do not presently handle either.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

And you spare the second if(sum > 9), just delete the else branch and always do % 10.
And in that vein, you can write carry = sum / 10 unconditionally.
Tanks for your feedback. I'm just confused about having to keep track of the tail. So the reason I need a tail is because sumOf and sumOf.next only gets initialized, and so I can't keep on adding to it unless if I have a tail?
@ithinkthat, the first digit gets assigned to sumOf. The second gets assigned to sumOf.next. The third should get assigned to sumOf.next.next, the fourth to sumOf.next.next.next, etc.. Instead of trying (and failing) to write enough cases to handle an arbitrary number of digits that way, you need to maintain a reference to whatever node it is at any given point whose next variable is supposed to receive the next digit. That's the last node in the linked list, also known as its "tail". Which node it is changes as you append nodes.
oh I see. That makes so much more sense now. Well, thanks for explaining.
0

Here is the solution, do note that i carry forward when the sum of two integers is greater than 9 else i continue with the sum of next integers from both the list.

class Node {
    private Object data;
    private Node next;
    public Object getData() { return data; }
    public void setData(Object data) {  this.data = data; }
    public Node getNext() { return next; }
    public void setNext(Node next) { this.next = next; }
    public Node(final Object data, final Node next) {
        this.data = data;
        this.next = next;
    }
    @Override
    public String toString() { return "Node:[Data=" + data + "]"; }
}


class SinglyLinkedList {
    Node start;
    public SinglyLinkedList() { start = null; }

    public void addFront(final Object data) {
        // create a reference to the start node with new data
        Node node = new Node(data, start);

        // assign our start to a new node
        start = node;
    }

    public void addRear(final Object data) {
        Node node = new Node(data, null);
        Node current = start;

        if (current != null) {
            while (current.getNext() != null) {
                current = current.getNext();
            }
            current.setNext(node);
        } else {
            addFront(data);
        }
    }

    public void deleteNode(final Object data) {
        Node previous = start;

        if (previous == null) {
            return;
        }

        Node current = previous.getNext();

        if (previous != null && previous.getData().equals(data)) {
            start = previous.getNext();
            previous = current;
            current = previous.getNext();
            return;
        }

        while (current != null) {
            if (current.getData().equals(data)) {
                previous.setNext(current.getNext());
                current = previous.getNext();
            } else {
                previous = previous.getNext();
                current = previous.getNext();
            }
        }
    }

    public Object getFront() {
        if (start != null) {
            return start.getData();
        } else {
            return null;
        }
    }

    public void print() {
        Node current = start;

        if (current == null) {
            System.out.println("SingleLinkedList is Empty");
        }

        while (current != null) {
            System.out.print(current);
            current = current.getNext();
            if (current != null) {
                System.out.print(", ");
            }
        }
    }

    public int size() {
        int size = 0;

        Node current = start;

        while (current != null) {
            current = current.getNext();
            size++;
        }
        return size;
    }

    public Node getStart() {
        return this.start;
    }

    public Node getRear() {
        Node current = start;
        Node previous = current;
        while (current != null) {
            previous = current;
            current = current.getNext();
        }
        return previous;
    }
}

public class AddNumbersInSinglyLinkedList {
    public static void main(String[] args) {
        SinglyLinkedList listOne = new SinglyLinkedList();
        SinglyLinkedList listTwo = new SinglyLinkedList();
        listOne.addFront(5);
        listOne.addFront(1);
        listOne.addFront(3);
        listOne.print();
        System.out.println();
        listTwo.addFront(2);
        listTwo.addFront(9);
        listTwo.addFront(5);
        listTwo.print();
        SinglyLinkedList listThree = add(listOne, listTwo);
        System.out.println();
        listThree.print();
    }

    private static SinglyLinkedList add(SinglyLinkedList listOne, SinglyLinkedList listTwo) {
        SinglyLinkedList result = new SinglyLinkedList();
        Node startOne = listOne.getStart();
        Node startTwo = listTwo.getStart();
        int carry = 0;
        while (startOne != null || startTwo != null) {
            int one = 0;
            int two = 0;
            if (startOne != null) {
                one = (Integer) startOne.getData();
                startOne = startOne.getNext();
            }
            if (startTwo != null) {
                two = (Integer) startTwo.getData();
                startTwo = startTwo.getNext();
            }
            int sum = carry + one + two;
            carry = 0;
            if (sum > 9) {
                carry = sum / 10;
                result.addRear(sum % 10);
            } else {
                result.addRear(sum);
            }
        }
        return result;
    }
}

Sample Run

Node:[Data=3], Node:[Data=1], Node:[Data=5]
Node:[Data=5], Node:[Data=9], Node:[Data=2]
Node:[Data=8], Node:[Data=0], Node:[Data=8]
Improve this answer

Comments

0 
**#In Python:-**

class Node():
    def __init__(self,value):
        self.value=value
        self.nextnode=None

class LinkedList():
    def __init__(self):
        self.head=None

    def add_element(self,value):
        node=Node(value)
        if self.head is None:
            self.head =node
            return
        crnt_node=self.head
        while crnt_node.nextnode is not None:           
            crnt_node=crnt_node.nextnode
        crnt_node.nextnode=node

    def reverse_llist(self):
        crnt_node=self.head
        if crnt_node == None:
            print('Empty Linkned List')
            return 
        old_node = None
        while crnt_node:
            temp_node = crnt_node.nextnode
            crnt_node.nextnode = old_node
            old_node = crnt_node
            crnt_node = temp_node
        self.head = old_node

    def converted_llist(self):
        crnt_node=self.head
        carry_value=0
        while True:
            #print(crnt_node.value)
            if (crnt_node.value+1)%10==0:
                carry_value=1
                crnt_node.value=0
                print(crnt_node.value,end='->')
            else:
                print(crnt_node.value+carry_value,end='->')
            if crnt_node.nextnode is  None:
                break
            crnt_node=crnt_node.nextnode
        print('None')

    def print_llist(self):
        crnt_node=self.head
        while True:
            print(crnt_node.value,end='->')
            if crnt_node.nextnode is None:
                break
            crnt_node=crnt_node.nextnode
        print('None')


list_convert=LinkedList()
list_convert.add_element(1)
list_convert.print_llist()
list_convert.add_element(9)
list_convert.print_llist()
list_convert.add_element(9)
list_convert.print_llist()
list_convert.add_element(9)
list_convert.print_llist()

list_convert.reverse_llist()
list_convert.print_llist()
list_convert.converted_llist()
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.